[USACO12MAR]摩天大楼里的奶牛（状态压缩DP）

题意

给出n个物品，体积为w[i]，现把其分成若干组，要求每组总体积<=W，问最小分组。(n<=18)

题解

一看以为是弱智题。（可能真的是，我太菜了）

然后跟walthou夸下海口：这么简单我做出来给你讲。

结果就被打脸了（对waithou说：我不会，自己看题解吧）

然后我就看了题解。。

设dp[i][j]为当前选i组已经选的情况为j的第i组的最小重量。

然后转移时，一个一个奶牛转移。

具体就是对于枚举的状态，如果dp[i][j]有不为INF，就枚举一个不属于j的x。

方程是

dp[i][j|(1<<x)]=min(dp[i][j|(1<<x)],dp[i][j]+a[x+1]);

dp[i+1][j|(1<<x)]=min(dp[i+1][j|(1<<x)],a[x+1]);

然后就没了（一开始18*2¹⁸*2¹⁸非用二次函数证明可以过，然后就A了一个点。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=999999999;
int n,w;
int a[20];
int dp[20][300000];
int main(){
    scanf("%d%d",&n,&w);
    int tot=(1<<n)-1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=tot;j++)
            dp[i][j]=INF;
    for(int i=0;i<=n-1;i++){
        dp[1][1<<i]=a[i+1];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=tot;j++)
            for(int x=0;x<=n-1;x++)
                if(dp[i][j]!=INF){
            //        cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
                    if(((1<<x)&j)==0&&dp[i][j]+a[x+1]<=w)dp[i][j|(1<<x)]=min(dp[i][j|(1<<x)],dp[i][j]+a[x+1]);
                    if(((1<<x)&j)==0)dp[i+1][j|(1<<x)]=min(dp[i+1][j|(1<<x)],a[x+1]);
                }
    //    cout<<dp[i][tot]<<endl;
        if(dp[i][tot]!=INF){
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}