BZOJ1226-学校食堂Dining

传送门
题意：中文题，非权限题。

Solution：
显然不能贪心，那么考虑dp，注意到 b[i]≤7 ，所以说可以考虑状压怎么做，再结合n<=1000，想到了一个状态：f[i][j][k]表示前i-1个人都吃过饭了，j表示后面7人和i的吃饭状态，上一个吃过饭的人是k。
转移：

f[i+1][j≫1][k]=f[i][j][k] (j&1==1,即i已经吃饭了)
f[i][j|(1≪t)][i+t]=f[i][j][k]+cal(i+t,k)

注意不要超过b[i],k那一维也可以优化成和i的差的形式，节省空间。

PS：状态到底怎么想呢…这个只能靠刷题了，想学好dp只能苦练啦~

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[1010][(1<<8)+5][20];
int n,T;
struct cai{
    int t,b;
}a[1010];
int cal(int x,int y)
{
    if (x<=0) return 0;
    return (a[x].t|a[y].t)-(a[x].t&a[y].t);
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (int i=0;i<=n+1;i++)
            for (int j=0;j<=15;j++)
                for (int k=0;k<(1<<8);k++)
                    f[i][k][j]=1e9;
        for (int i=1;i<=n;i++)
            scanf("%d%d",&a[i].t,&a[i].b),a[i].b=min(a[i].b,n-i);
        f[1][0][7]=0;
        for (int i=1;i<=n;i++)
        {
            for (int j=0;j<(1<<8);j++)
                for (int k=-8;k<=7;k++)
                {
                    if (f[i][j][k+8]<1e9)
                    {
                        if (j&1)
                        {
                            f[i+1][j>>1][k+7]=min(f[i+1][j>>1][k+7],f[i][j][k+8]);
                            continue;
                        }
                        int maxn=7;
                        for (int now=0;now<=maxn;now++)
                        {
                            if (((1<<now)&j)==0)
                            {
                                f[i][(1<<now)|j][now+8]=min(f[i][(1<<now)|j][now+8],f[i][j][k+8]+cal(k+i,i+now));
                                maxn=min(maxn,now+a[i+now].b);
                            }
                        }
                    }
                }
        }
        int anss=1e9;
        for (int i=-8;i<=-1;i++)
        {
            //cout<<anss<<endl;
            anss=min(anss,f[n+1][0][i+8]);
        }
        printf("%d\n",anss);
    }
}