題意：

$n$個人排隊打飯，第$i$個人口味$a_i$，能容忍最多身后第$b_i$個人先打飯。

先后兩人$i,j$做飯時間為$a_i & a_j - a_i | a_j$

求最少時間

---

?

一開始想$f[i][s]$表示第$i$個人身后人吃飯集合$s$，第$i$個人最后吃完的狀態，發現沒法轉移

這時候應該考慮給狀態加維

$f[i][s][k]$表示前$i-1$人吃完，$i$身后包括$i$的吃飯集合為$s$，最后一個吃完的人是$k$的最短時間

如果$i$吃完了，可以直接轉移到$i+1$；否則枚舉下一個誰吃飯，注意滿足容忍度要求

還有一點重要：$f[i]$的時候集合$s$是可以出現大于$b[i]$的人吃完飯的，因為$s$中的$i$有可能已經吃完飯了

?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N=1005,S=(1<<8)+5,INF=1e9; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int n,a[N],b[N]; inline int w(int i,int j){return i<=0 ? 0 : (a[i]|a[j]) - (a[i]&a[j]); } int f[N][S][16],Z=8; int main(){freopen("in","r",stdin);int T=read();while(T--){n=read();for(int i=1;i<=n;i++) a[i]=read(),b[i]=min(read(),n-i);memset(f,127,sizeof(f));f[1][0][Z-1]=0;for(int i=1;i<=n;i++){int All=1<<8;for(int s=0;s<All;s++) for(int k=-8;k<=7;k++) if(f[i][s][k+Z]<INF){int now=f[i][s][k+Z];if(s&1) {int &t=f[i+1][s>>1][k-1+Z];t=min(t,now);continue;}int lim=7;for(int j=0;j<=lim;j++) if( ((1<<j)&s)==0 ){int &t=f[i][s|(1<<j)][j+Z];t=min(t,now+w(i+k,i+j));lim=min(lim,j+b[i+j]);}}}int ans=INF;for(int k=-8;k<=-1;k++) ans=min(ans,f[n+1][0][k+Z]);printf("%d\n",ans);} }

?

總結

以上是生活随笔為你收集整理的BZOJ 1226: [SDOI2009]学校食堂Dining [DP 状压]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。