牛客寒训营3 C(倒着dp?)

题目 题意: 和B题反过来，给定dp数组，反推输入。 思路: 莫得思路。看了题解，说对原dp数组求个逆。 f[i][j] = f[i-1][j] + f[i-1][j - a[i]/2] + f[i-1][j - a[i]] f[i+1][j] = f[i][j] + f[i][j - a[i]/2] + f[i][j - a[i]] 由题意，西瓜都是偶数。f[1]即重量为2的瓜的数量. 当dp[i] != f[cnt][i]时,向数组中添加i * 2的西瓜，相等时则i++，探索下一个体积是否满足。可以类比01背包把第一维压掉. 时间复杂度: O(n*m). 代码:

// Problem: 智乃买瓜(another version)
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23478/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i