bzoj 1226: [SDOI2009]學校食堂Dining

狀态壓縮 轉移判斷

dp不一定是轉移到i就要對i進行處理  可以表示一個範圍 且同層i也可以互相轉移

/**************************************************************
    Problem: 1226
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:2508 ms
    Memory:21828 kb
****************************************************************/
 
/*
滿足忍耐度就枚舉忍耐度的範圍 選取可行的忍耐度
f i,j,k 表示前i-1的人已經拿到飯  (本次給i做菜
    j表示i～i+bi的狀态 k表示上一次拿到飯菜的人相對i的位置
j的取值是 0～2^8-1 k的取值是-7~7  為了友善 整體+8
NOTE:第一道菜是不需要計算時間的
*/
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1050;
int f[N][1<<8][20],n,t[N],b[N],res,inf,T;
int clac(int i,int k,int l)
{
    if(i+k==0) return 0;  // 判斷一下k是不是從位置0轉移過來的
    return (t[i+k]^t[i+l]);
}
void getmin(int&a,int b) {if(a>b) a=b;}
int main()
{
    scanf("%d",&T); while(T--)
    {
        scanf("%d",&n); res=0x3fffffff;
        for(int i=1;i<=n;i++) scanf("%d%d",&t[i],&b[i]);
        memset(f,0x3f,sizeof(f)); inf=f[0][0][0]; f[1][0][7]=0; 
//f[1][0][7] 7表示7-8=-1 就是1後面一 也就是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]!=inf) // 
        {
            if(j&1&&k!=-8) getmin(f[i+1][j>>1][k+8-1],f[i][j][k+8]);
// 第i位已經就緒 就可以任意選擇k 直接往後面轉移就行了
// 否則沒辦法轉移到i+1 （因為fi的含義是1～i-1全部就緒）
// 就隻有枚舉本次由誰來打飯 不過又要滿足i之後人的忍耐值  是以維護一個maxr 美劇大于maxr就break
            else
            {
                int maxr=n;
                for(int l=0;l<=7;l++) if(!((1<<l)&j)) //枚舉的前提是這個沒有被安排
                {
                    if(i+l>maxr) break; // 适當break
                    getmin(maxr,i+l+b[i+l]);//更新maxr
                    getmin(f[i][j|(1<<l)][l+8],f[i][j][k+8]+clac(i,k,l));
                }
            }
        }
        for(int k=-8;k<=-1;k++) getmin(res,f[n+1][0][k+8]); printf("%d\n",res);
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/lxy8584099/p/10436171.html