一道貪心+類背包DP的好題

首先發(fā)現(xiàn)一個(gè)十分顯然的性質(zhì)，沒有這個(gè)性質(zhì)整道題目都難以下手：

無論兩隊(duì)的順序如何，總是讓吃飯慢的人先排隊(duì)

這是一個(gè)很顯然的貪心，因?yàn)槿绻尦燥埪呐旁诤竺嬉嗟臅r(shí)間至少?zèng)]有這樣優(yōu)

因此我們先按吃飯時(shí)間從大到小sort一下

然后我們發(fā)現(xiàn)這是一個(gè)類01背包的DP，只不過這里的狀態(tài)要么是01，要么是10（即要么在1隊(duì)，要么在2隊(duì)）

然后這種東西都有一些很神奇的性質(zhì)，比如說我們用前綴和sum[i]表示前i個(gè)人中排隊(duì)的總時(shí)間，那么

sum[i]-前i個(gè)人中去1號(hào)窗口的人的打飯時(shí)間之和=前i個(gè)人中去1號(hào)窗口的人的打飯時(shí)間之和

然后我們可以想出一個(gè)DP，用f[i][j]表示前i個(gè)人中，在1號(hào)窗口排隊(duì)的人共花了j分鐘排隊(duì)的最優(yōu)情況下，最少要多少時(shí)間（要和2號(hào)窗口的取一個(gè)min），包括吃飯的時(shí)間

然后就有轉(zhuǎn)移：

• f[i][j]=min(f[i][j],max(f[i-1][j-a[i].t],j+a[i].e))（在1號(hào)窗口打飯）

• f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+a[i].e)（在2號(hào)窗口打飯）

然后我們發(fā)現(xiàn)這個(gè)可以滾動(dòng)存儲(chǔ)不過也沒這個(gè)必要，但是我還是寫了

CODE

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=205; struct data {int t,e; }a[N]; int n,f[2][N*N],sum[N],ans; inline char tc(void) {static char fl[100000],*A=fl,*B=fl;return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++; } inline void read(int &x) {x=0; char ch=tc();while (ch<'0'||ch>'9') ch=tc();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc(); } inline bool comp(data a,data b) {return a.e>b.e; } inline int min(int a,int b) {return a<b?a:b; } inline int max(int a,int b) {return a>b?a:b; } int main() {//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);register int i,j;for (read(n),i=1;i<=n;++i)read(a[i].t),read(a[i].e);sort(a+1,a+n+1,comp);for (i=1;i<=n;++i)sum[i]=sum[i-1]+a[i].t;memset(f[0],63,sizeof(f[0])); f[0][0]=0;for (i=1;i<=n;++i){int now=i&1,last=now^1;memset(f[now],63,sizeof(f[now])); ans=f[now][0];for (j=sum[i];j>=0;--j){if (j>=a[i].t) f[now][j]=min(f[now][j],max(f[last][j-a[i].t],j+a[i].e));if (sum[i]-j>=a[i].t) f[now][j]=min(f[now][j],max(f[last][j],sum[i]-j+a[i].e));}}for (i=0;i<=sum[n];++i)ans=min(ans,f[n&1][i]);printf("%d",ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/cjjsb/p/9016515.html

總結(jié)

以上是生活随笔為你收集整理的Luogu P2577 [ZJOI2005]午餐的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。