P3052(摩天大楼里的奶牛CowsinaSkyscraper一维状压dp状态也有顺序)

题目
注意&＃xff1a;res[S]:状态S下最后一组的剩余体积.
这个状压dp 从状态res[i]向状态res[i|(1<<(j-1))]转移是每次都放res[i]放好的物品的最后面&＃xff0c;是有顺序的。这样利用res数组才是对的。然后res[i|(1<<(j-1))]放同样的物品会被很多种顺序都更新到。所以状压dp合理行显而易见了。

#include
#include
using namespace std;
const int N&＃61;18,INF&＃61;0x3f3f3f3f;
int dp[(1<<N)&＃43;5],res[(1<<N)&＃43;5],v[N&＃43;5];//res[S]:状态S下最后一组的剩余体积
int main(){int n,w,t;scanf("%d%d",&n,&w);t&＃61;(1<<n);for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) scanf("%d",&v[i]);for(int i&＃61;1;i<t;&＃43;&＃43;i) dp[i]&＃61;n;//初始化为>&＃61;n的数 相当于INFdp[0]&＃61;1,res[0]&＃61;w;//初始化for(int i&＃61;0;i<t-1;&＃43;&＃43;i){for(int j&＃61;1;j<&＃61;n;&＃43;&＃43;j){if(i&(1<<(j-1))) continue;int d&＃61;(i|(1<<(j-1)));if(res[i]>&＃61;v[j]&&dp[i]<&＃61;dp[d]){if(dp[i]<dp[d]) res[d]&＃61;res[i]-v[j];else res[d]&＃61;max(res[d],res[i]-v[j]);dp[d]&＃61;dp[i];}if(res[i]<v[j]&&dp[i]&＃43;1<&＃61;dp[d]){if(dp[i]&＃43;1<dp[d]) res[d]&＃61;w-v[j];else res[d]&＃61;max(res[d],w-v[j]);dp[d]&＃61;dp[i]&＃43;1;}}}printf("%d\n",dp[t-1]);
}