状压dp-基础题目2（[USACO12MAR] Cows in a Skyscraper G）

题目链接做题反思这题我一开始没过Subtask #1当时想的是dp数组存储电梯承载奶牛集合s二进制转整数需要的最少趟数再开一个数组z存储奶牛集合s的重量如果z[s]w,则让z[s]%w。这是不对的比如Subtask #1的数据最大载重w为104头奶牛的重量为9992用这个思路答案是3。问题就在于这种做法会把奶牛“分身”乘坐电梯比如前两头奶牛有一头奶牛会有1重量在1趟电梯另外8重量在另一趟电梯这就有问题了。题目正解数组定义我们定义一个数组dpdp[i][j]表示第i趟运送奶牛集合j的重量。初始化dp数组为0x3f3f3f3f,dp[0][0]0,dp[1][1(i-1)]c[i]。状态转移外层遍历趟数循环遍历为i范围是1至n。内层循环遍历集合j范围0至(1n),我们看一下用i趟运送奶牛集合j是否能实现如果可以则再遍历新加入奶牛循环变量k范围是1至n。通过移位运算和与运算判断集合j时候有奶牛k如果没有就看一下当前dp[i][j]c[k]是否大于w如果是要新开一趟dp[i1][j|(1(k-1))]min(dp[i 1][j | (1 k - 1)],c[k])否则 dp[i][j | (1 k - 1)] min(dp[i][j | (1 k - 1)], dp[i][j] c[k])。输出答案循环变量i遍历1至n输出第一个dp[i][(1n)-1]0x3f3f3f3f的值结束。AC代码#includebits/stdc.husingnamespacestd;intw,c[20],dp[20][120],n;intmain(){cinnw;memset(dp,0x3f,sizeof(dp));dp[0][0]0;for(inti1;in;i){cinc[i];dp[1][1(i-1)]c[i];}for(inti1;in;i){for(intj0;j(1n);j){if(dp[i][j]0x3f3f3f3f){for(intk1;kn;k){if(!((1k-1)j)){if(dp[i][j]c[k]w)dp[i1][j|(1k-1)]min(dp[i1][j|(1k-1)],c[k]);elsedp[i][j|(1k-1)]min(dp[i][j|(1k-1)],dp[i][j]c[k]);}}}}}for(inti1;in;i){if(dp[i][(1n)-1]0x3f3f3f3f){couti;break;}}return0;}