题解：P10961 划分大理石

设 \(f_x\) 表示拼成 \(x\) 后，当前的大理石最多还能剩下几块，不能拼成就是 \(-1\)。

状态转移（当前考虑的大理石价值为 \(i\)，有 \(x\) 块）：

\(f_j=x(f_j\ge0)\) 本来就可以拼成，那么现在的大理石都可以剩下。

\(f_j=f_{j-i}-1(f_j=-1,j\ge i,f_{j-i}>0)\) 本来不能拼成，但用了一块就能拼成了。

\(f_j=-1\) 除了上述两种情况，都不能拼成。

最后时间复杂度为 \(O(m)\)。\(m\) 是可能的最大价值（这里就是 \(20000\times6=120000\)）。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define MAXN 120011
ll f[MAXN],x;
int main() {
	while(1) {
		memset(f,-1,sizeof f);
		f[0]=0;
		ll sum=0;
		for(ll i=1; i<=6; ++i) {
			cin>>x;
			sum+=x*i;
			for(ll j=0; j<MAXN; ++j) {
				if(f[j]>=0)f[j]=x;
				else if(j>=i&&f[j-i]>0)f[j]=f[j-i]-1;
				else f[j]=-1;
			}
		}
		if(!sum)break;
		puts(!(sum&1)&&f[sum>>1]>=0?"Can":"Can't");
	}
	return 0;
}