#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;int dp[100000];int main(){int a[11],sum,v,i,j,k,cnt,cas = 1;while(~scanf("%d",&a[1])){sum = a[1];for(i = 2;i<=6;i++){scanf("%d",&a[i]);sum+=i*a[i];}if(!sum)break;printf("Collection #%d:\n",cas++);if(sum%2)//總和為奇數(shù)，必定不能平分{printf("Can't be divided.\n\n");continue;}v = sum/2;memset(dp,0,sizeof(dp));dp[0] = 1;for(i = 1;i<=6;i++){if(!a[i])continue;for(j = 1;j<=a[i];j*=2)//二進(jìn)制優(yōu)化{cnt = j*i;for(k = v;k>=cnt;k--){if(dp[k-cnt])//必須前面的能夠放入背包，現(xiàn)在的才能放入背包dp[k] = 1;}a[i]-=j;}cnt = a[i]*i;//剩下的if(cnt){for(k = v;k>=cnt;k--){if(dp[k-cnt])dp[k] = 1;}}}if(dp[v])printf("Can be divided.\n\n");elseprintf("Can't be divided.\n\n");}return 0;}謝謝!急求!!各位大佬能回答一下嗎
2 回答
慕碼人2483693
TA貢獻(xiàn)1860條經(jīng)驗(yàn) 獲得超9個贊
var dp:array[0..100000]of longint;
a:array[0..11]of longint;
sum,i,v,j,k,cnt,cas
begin
cas:=1;
while (not eoln) do
begin
read(a[1]);
sum:=a[1];
for i:=2 to 6 do
begin
read(a[i]);
sum:=sum+i*a[i];
end;
if (sum=0) break;
writeln("Collection #%d:",cas++);
if(sum mod 2=1)
begin
writeln("Can't be divided.");
continue;
end;
v:=sum div 2;
fillchar(dp,0,sizeof(dp));
dp[0]:=1;
for i:=1 to 6 do
begin
if(a[i]=0) continue;
j=1;
while (j<=a[i]) do
begin
cnt:=j*i;
for k:=v downto cnt do
if(dp[k-cnt]) dp[k] = 1;
a[i]=a[i]-j;
j:=j*2;
end;
cnt:=a[i]*i;
if (cnt=1)
begin
for k:=v downto cnt do
if (dp[k-cnt]=1) dp[k]=1;
end;
end;
if (dp[v]=1) writeln("Can be divided.")
else writeln("Can't be divided.\n\n");
end;
end.
自己改一下吧，沒有編譯器，sorry了，不會的問我
-
慕萊塢9195162NOIp普及組……
- 2 回答
- 0 關(guān)注
- 870 瀏覽
添加回答
舉報
0/150
提交
取消