题意：烤一块牛排。牛排有两面，要求每面都烤刚好n分钟。给出k个时间段，在这个时间段内可以给牛排翻任意次面。求最少翻多少次面能烤出符合要求的牛排，如果烤不出，输出Hungry。
解：首先牛排不烤上面就烤下面，所以拿一个的时间设状态就可以了，不妨选择上面。先设dp[i][j]为第i分钟时，上面烤了j分钟时最少反面次数，但这样目测是O(n2)的，并且没有用到时间段，不妥。重设dp[i][j]为到第i个时间段结束，上面烤了j分钟的最少次数。接下来考虑转移。先观察一下烤的过程，肯定不可能翻任意次面。设可以翻面的时间段长为period，翻一次面使得两面各烤k和period-k，同时烤的面变化；翻两次面也使得两面各烤k和period-k，但烤的面不变。翻两次以上面可以变成两次以内的情况。如果上一次结束在烤上面，那本次会被烤k+l[i]-r[i-1]分钟，翻一次面；如果上次结束在烤下面，本次会被烤k分钟，翻两次面。
由此可见有两次转移，分别遍历 [ j-period, j ]和[ r[i]-j-period, r[i]-j ]，可以用单调队列优化。 第二个因为j前面是负号，所以倒着遍历。
代码：
#include <bits/stdc++.h> using namespace std; #define maxx 1005 #define maxn 25 #define maxm 205 #define ll long long #define inf 1000000009 #define mod 2520 int q[200005]={0}; int l[105]={0},r[105]={0}; int dp[2][200005]={0}; signed main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=k;i++){ scanf("%d%d",&l[i],&r[i]); } memset(dp,0x7f,sizeof dp); dp[0][0]=0; int z=1; for(int i=1;i<=k;i++){ int period=r[i]-l[i]; for(int j=0;j<=n;j++){ dp[z][j]=dp[1-z][j]; } int head=1,tail=0; for(int j=0;j<=min(n,r[i]);j++){ while(head<=tail&&q[head]<j-period) head++; while(head<=tail&&dp[1-z][q[tail]]>=dp[1-z][j]) tail--; q[++tail]=j; dp[z][j]=min(dp[z][j],dp[1-z][q[head]]+2); } head=1,tail=0; for(int j=r[i];j>=0;j--){ while(head<=tail&&q[head]<r[i]-j-period) head++; while(head<=tail&&dp[1-z][q[tail]]>=dp[1-z][r[i]-j]) tail--; q[++tail]=r[i]-j; dp[z][j]=min(dp[z][j],dp[1-z][q[head]]+1); // for(int kk=0;kk<=period;kk++){ // if(r[i]-j-kk>=0) dp[i][j]=min(dp[i][j],dp[i-1][r[i]-j-kk]+1); // if(j-kk>=0) dp[i][j]=min(dp[i][j],dp[i-1][j-kk]+2); // } } z=1-z; } if(dp[1-z][n]==0x7f7f7f7f){ printf("Hungry"); return 0; } printf("Full\n"); printf("%d\n",dp[1-z][n]); return 0; } //dp[i][j] to the i th period, the cutlet has been fried j second for one side //dp[i][j]=min(dp[i-1][j-h[i]-k]+1) k is in period i
View Code
然后口胡一下CodeForces – 1304F2 Animal Observation (hard version)
题意：给出一个矩阵，每行选一个格子作为一个2*k小矩阵的左上角。最后一行只要选1*k的小矩阵就可以。求所有所有小矩阵里数之和的最大值。如果矩阵重叠，重叠部分的数只作一次贡献。
解：显然设dp[i][j]为第i行选第j个格子时能取得的最大值。转移时分两种情况，一是和上面没重叠，直接取最大值；二是和上面重叠，减去重复部分取最大值。线段树和单调队列都可以做到。
原文地址：http://www.cnblogs.com/capterlliar/p/16908705.html
