#C241010A. 子集背包

标签（Label）

• 动态规划

网址（Website）

题目详情 - 子集背包 - Super

题解 - 子集背包 - Super

题解（Solution）

$\qquad$呜呜，被动态规划击破特攻了~qwq

$\qquad$设 $f_{i,j}$ 表示第 $i$ 个物品，选了 $j$ 的质量，则如果 $j\ge a_i$ ，就把 $f_{i,j}$ 翻倍或者从 $f_{i-1,j-a_i}$ 转移，否则就只能从 $f_{i,j}$ 转移。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<stack> 
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	bool f=false;char c;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 4005;
const int A = 10005;
bool ST;

int n,V,ans,a[N];
int f[2][A];

inline void add(int &x,int y){if((x+=y)>=mod) x%=mod;}
int bas[N];

inline void solve(){
	n = rd(), V = rd();
	For(i,1,n) a[i] = rd();
	bas[0] = 1;For(i,1,n) bas[i] = 1ll*bas[i-1]*2%mod;
	
	f[0][0] = 1;
	For(k,1,n){//枚举物品
		int p = k&1, b = (k&1)^1;
		Rof(j,V,a[k]){//物品的质量 
			f[p][j] = (f[b][j]*2 + f[b][j-a[k]])%mod;
		}
		Rof(j,a[k]-1,0){
			f[p][j] = f[b][j]*2%mod;
		}
	}
	printf("%lld\n",f[n&1][V]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}