正文之前的一段话：假期马上就结束了，要回去上学了！
话说，开学之后，学校里估计得被挤爆了，那么多人，以前的惬意生活估计一去不复返了。（据说食堂吃饭都要抢饭，真的醉了）
不过也好，和其它学院的兄弟姐妹们在一起，也可以互相学习吧？
本来假期我是有个自己的计划的，但是学长们搞了小训练赛，每天5到10个题，做完就啥也不想干了。。。。而且导致脑子一团混乱。
在这里整理一下我现在对DP新的理解吧。
①有关DP的本质
dp，就是动态规划。在我现在的理解里，这种类型的算法必须基于以下条件：
1.最终结果可以由某几个变量对应，中间过程也可以被对应，叫做状态。
2.某个状态可以通过一些变换得到其他状态。
3.各个状态唯一，且互相不受影响。（无后效性）
（不太会说。。大概有了以上三点，就可以着手设计状态转移方程了）
有了状态转移方程，我们就可以把一个状态变为另一个状态，这个方程必须是普适的，形式是多样的。
除了转移方程以外，初始态和结束态也是十分重要的！
下面举一个例子吧。。
CodeForces – 698A Vacations
Vasya有n天的假期，这n天里，有某些特定的日子体育馆开门，有某些特定的日子cf有比赛(也有可能某天都没有，也有可能都有)。Vasya不能在一天里同时去体育馆和打比赛，也不能连续两天去体育馆，或者连续两天打比赛。如果他不干这两件事，他就只能休息。给出哪些天体育馆开门，哪些天有比赛，求Vasya的最少休息天数。
第一步，判断是不是DP。
第一反应，我们用天数对应答案。但是这一天干了什么对后一天的答案有影响。
所以，我们用【天数】和【这一天干了什么】对应答案，这样就是满足以上三点的。知道天数，知道前一天干了什么，就能推出后一天的答案。
第二步，设计状态转移方程。
把刚刚的思路抽象化，设f[i][j]为前i天，第i天干的事情为j情况下的最少休息天数。
j=0 gym，j=1 contest，j=2 rest
那么:
若j!=2 f[i][j]=min(f[i-1][k]) k!=j或k==2 并且j活动必须符合第i天的条件 否则不能转移
若j=2 f[i][j]=min(f[i-1][k])+1
这样看这个转移方程恶心的不行，但是实际写起来还是很好的，有一些过于抽象的转移方程，为了节省时间，可以不写那么严谨，或者写成记忆化搜索。
第三步，明确初始状态和最终状态
这个题比较显然 f[0][2]=0 其他都是inf
最终答案是min(f[n][0],f[n][1],f[n][2])
至此，观察一下时间复杂度，O(N)，可以做，整道题的思路就通了。
如果发现时间复杂度不行。。那么考虑优化或者重新划分状态。
然后就可以写代码啦：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int N=105; int f[N][4];//第几天 做gym contest rest int s[N],n; int main() { scanf("%d",&n); for(int i=1;i< =n;i++)scanf("%d",&s[i]); memset(f,0x3f,sizeof f);f[0][2]=0; for(int i=1;i<=n;i++) { f[i][2]=min(f[i-1][2],min(f[i-1][0],f[i-1][1]))+1;//rest if(s[i]==1)f[i][1]=min(f[i-1][0],f[i-1][2]);//contest if(s[i]==2)f[i][0]=min(f[i-1][1],f[i-1][2]);//gym if(s[i]==3) { f[i][1]=min(f[i-1][0],f[i-1][2]);//contest f[i][0]=min(f[i-1][1],f[i-1][2]);//gym } } printf("%d\n",min(f[n][0],min(f[n][1],f[n][2]))); }
这里没有用j循环，而是手动写的，可能思路会清晰一些。
②记忆化搜索
做了几个题之后，感觉记忆化搜索和dp本质一样，但是思路是完全不同的。
记忆化搜索是一种搜索，找到最终结果之后，回溯回去。
dp是拿到一个状态，顺着推出最终状态。
记忆化搜索之所以可以“记忆化”，还是因为可以被划分为状态、无后效性(与dp)一样。
一般有两种情况会很顺畅的想出记忆化搜索。
第一种是在爆搜的时候发现可以记忆化：
CodeForces – 39E What Has Dirichlet Got to Do with That?
两个人以最优策略玩游戏，规则如下：
把a个物品放到b个盒子里，盒子可以空。物品和盒子都不同。
一开始有a个物品和b个盒子和一个常数n，轮到某个人开始玩时，他必须增加一个物品或者增加一个盒子（不能什么也不做），使得把a个物品放到b个盒子里的方案数变为k，若k>=n，则当前玩家就输掉了。
所以这两个人轮流以最优策略进行操作，问最后谁赢，或者平局。
首先【把a个物品放到b个盒子里，盒子可以空。物品和盒子都不同】是一个高中数学问题。。答案显然是b^a。
对于完全不知道这种博弈题怎么做的我来说，第一反应是爆搜。。1代表赢 0为输 2平局
我们以a,b为参数开始爆搜，如果b^a>=n 那么直接返回0
先不考虑平局情况
否则就递归下去 dfs(a+1,b) dfs(a,b+1)
如果返回上来有0 能胜了 我们就选取这个最优策略 返回1
如果返回上来没有0 但是有2 就是能平局 就能保证自己不输 返回2
否则返回0
那么啥时候平局呢？b==1的时候
考虑b==1 并且 (b+1)^a>=n 时 我们只能增加a来确保自己不输，但是因为b==1，无论两人怎么增加a，都不会分出胜负，这时就平局了！
这时爆搜就写好了，我们观察这个爆搜函数，dfs(a,b)的答案只和a b有关，不和外部变量有关，这时，就可以设数组f[a][b]，进行记忆化搜索了！
我们从这里得出结论，只要是不借助外部变量的搜索，都可以改成记忆化搜索，复杂度为状态总数*每次搜索的复杂度
下面是代码：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N=100005; int f[N][55]; long long n; int a,b; bool judge(long long a,long long b) { long long ret=1; for(int i=1;i< =b;i++) { ret*=a; //cout<<ret<<endl; if(ret>=n)return 1; } return 0; } int dfs(int a,int b) { //cout< <a<<" "<<b<<" "<<judge(a,b+1)<<endl; if(f[a][b]!=-1)return f[a][b]; if(judge(a,b))return f[a][b]=1;//当前输掉 if(a==1&&judge(a+1,b))return f[a][b]=2; int l=dfs(a+1,b),r=dfs(a,b+1); if(l==0||r==0)return f[a][b]=1; if(l==2||r==2)return f[a][b]=2; return f[a][b]=0; } int main() { cin>>a>>b>>n; memset(f,-1,sizeof f); int ans=dfs(a,b); if(ans==2)puts("Missing"); else puts(ans==1?"Masha":"Stas"); return 0; } //</algorithm></cstdio></cstring></iostream>
代码高亮插件出了点小问题。。还在排查。。
还有另一道题，是优化记忆化搜索的。
优化，无非是优化转移复杂度和状态复杂度。
CodeForces – 729F Financiers Game
还是两个人以最优策略轮流玩游戏。
有一个数列，一个人从数列开头取数字，并希望两人取出数字总和的差值最大，一个人从数列结尾取数字，并希望两人取出数字总和的差值最小。
每个人取的数字的数量为k或k+1，其中k为上一个人取出数字的数量，第一个取数字的人可以取出1个或两个数字。
当某个人想要取的数量大于剩余数字数量时，游戏停止。
求两人取出数字的差值为多少。
这题充满了隐含条件。。。
首先考虑搜索，dfs(l,r,p,q) 区间l到r,当前取数的数量为p,当前取数的人为q，比较显然。
发现答案只和l,r,p,q有关，考虑加上记忆化。
我们发现这题数据范围是4000 4000*4000*4000*2 爆了啊！
但是！可达鸭发现事情并不是这么简单！
假设这俩人每次都比上一次取的数多，也就是1+2+3+4+… 但是加到90的时候，就已经超过4000了，也就是说，这俩人每次取的数的数量在[1,90]之间。
所以复杂度变成了4000*4000*90*2
但是！可达鸭又一次发现事情并不是这么简单！
每个人只会从自己的那一边取，而且每次最多只会多取一个，所以每个人只会取自己那半边的！
所以复杂度变成2000*2000*90*2 空间复杂度同样减少 看上去快要可以做了(cf评测机超快，据说1e8都能过)
但是！可达鸭再一次发现事情并不是这么简单！
每个人每次最多只会多取一个，所以这两个人取数的位置相对于起始位置的差值非常接近！
即abs(l-(n-r+1))< =90 我们用一个变量记录l-n+r就行啦！每次转移时维护这个值。
至此，复杂度变为2000*90*90*2 可以过了！
这就是利用记忆化搜索来减少状态表示的复杂度。因为记忆化搜索不用刻意注意转移顺序，所以优化要方便很多。
代码
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<bitset> using namespace std; //f[l][len][k][q] 起点为l 计数器为Len 上次选了k个 是否为左侧 const int N=2100; int f[N][105][105][2],n,s[N*2]; int dfs(const int l,const int len,const int k,const int q) { int r=n-len-l+1; if(r-l+1<k )return 0; if(f[l][len][k][q]!=-1)return f[l][len][k][q]; //cout<<l<<" "<<r<<" "<<k<<" "<<q<<endl; int ret; if(q==1)//左选 { ret=-0x7fffffff; if(k<=r-l+1)ret=max(dfs(l+k,len-k,k,0)+s[l+k-1]-s[l-1],ret); if(k+1<=r-l+1)ret=max(dfs(l+k+1,len-k-1,k+1,0)+s[l+k]-s[l-1],ret); } else { ret=0x7fffffff; if(k<=r-l+1)ret=min(dfs(l,len+k,k,1)-(s[r]-s[r-k]),ret); if(k+1<=r-l+1)ret=min(dfs(l,len+k+1,k+1,1)-(s[r]-s[r-k-1]),ret); } f[l][len][k][q]=ret; return ret; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x=0;scanf("%d",&x); s[i]=s[i-1]+x; } memset(f,-1,sizeof f); printf("%d\n",dfs(1,0,1,1)); return 0; }
下面说一个记忆化搜索方便转移的
poj 3186
给一个数列，每次可以在开头或者结尾取一个数t，第i次取出数获得的收益为i*t，求最大收益。
很显然是区间dp。如果直接写dp的话，我们需要考虑dp的顺序(其实也很简单)
我们直接考虑记忆化搜索，是非常好写的！
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<queue> using namespace std; const int N=2005; long long f[N][N]; int n,a[N]; long long dfs(int l,int r) { if(f[l][r]!=-1)return f[l][r]; if(l==r)return f[l][r]=n*a[l]; long long now=l-1+n-r+1; long long x=now*a[l]+dfs(l+1,r); long long y=now*a[r]+dfs(l,r-1); return f[l][r]=max(x,y); } int main() { scanf("%d",&n); memset(f,-1,sizeof f); for(int i=1;i< =n;i++)scanf("%d",&a[i]); cout<<dfs(1,n)<<endl; return 0; }
代码简洁，思路清晰！
③dp中的一些思路
1.辅助数组帮助优化转移
HDU1024
给出一个长度为n的数列，要求从这个数列中找出m个子串，使得子串的和最大。n< =1000000 m很小
很容易(想了半天)想到状态表示f[i][j]为前i个子串，结尾为j时的最大子串和(j必须要选)。
转移就是要么加到原来的串里，要么新开一串。
f[i][j]=max(f[i][j-1],f[i-1][k])+s[j] 但是这样复杂度是(n^2)*m 过不了，要优化。
我们发现，在dp中，当我计算完i-1那一行的时候，我是可以同时算出i-1这一行的f[i-1][k]的最大值。
我们令mx[j]=max(f[i-1][k]) (k< =j) 在计算f[i-1][j]时就预处理出来。
现在发现空间可能会爆，那么直接扔掉i这一维，把数组写成f[j]。
最后的转移方程:
f[j]=max(f[j-1],mx[j-1])+s[j]
mx[j]=max(f[k]) k<=j
这里辅助数组减少了大量冗余计算，相当于用空间换时间。
/* f[i][j] 前i组 以j结尾 mx[j]=max(f[i-1][k]) k< =j f[i][j]=max(f[i][j-1],mx[j-1]); */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int N=1000005; int f[N],s[N]; int mx[N]; int n,m; int main() { while(scanf("%d%d",&m,&n)!=EOF) { for(int i=1;i< =n;i++)scanf("%d",&s[i]); memset(f,0,sizeof f); memset(mx,0,sizeof mx); for(int i=1;i<=m;i++) { f[i]=0; for(int j=i;j<=n;j++) { f[j]=max((i<=j-1)?f[j-1]:-0x7fffffff,mx[j-1])+s[j]; } mx[i-1]=-0x7fffffff; for(int j=i;j<=n;j++) mx[j]=max(mx[j-1],f[j]); } int ans=-0xfffffff; for(int i=m;i<=n;i++)ans=max(ans,f[i]); printf("%d\n",ans); } return 0; } /* 3 10 -1 2 -4 -6 -1 2 3 4 0 10 */
2.利用初始状态不同，顺序不同，得到不同结果。
最经典的就是背包问题。
完全背包为保证每种物品可以用很多次，就01背包的把i，j循环反过来。
而要求恰好装满的背包则是把所有位置都付初始值inf，而f[0]=0。这样保证每次转移都从已经装过的位置转移而来，不会留下空隙。
HDU 1114
给出一个存钱罐的重量，以及里面可能的钱的种类。每种钱有自己的重量和面值，求这个存钱罐里的钱的总价值的最小值。
非常显然的完全背包，并且要求恰好装满。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> using namespace std; const int N=10005,M=505; int f[N],n,m,s[M],w[M],cnt; int main() { scanf("%d",&cnt); while(cnt--) { int t1,t2; scanf("%d%d",&t1,&t2); m=t2-t1; scanf("%d",&n); for(int i=1;i< =n;i++)scanf("%d%d",&w[i],&s[i]); memset(f,0x3f,sizeof f); f[0]=0; for(int i=1;i<=n;i++) for(int j=s[i];j<=m;j++) f[j]=min(f[j],f[j-s[i]]+w[i]); if(f[m]!=0x3f3f3f3f) printf("The minimum amount of money in the piggy-bank is %d.\n",f[m]); else puts("This is impossible."); } return 0; }
3.巧妙设计状态表示
poj 1661
中文题。。
一开始想用平台来表示状态，但是发现平台有长度，没法用“第i个平台”来表示jimmy的准确位置。
但是我们发现，jimmy从某个平台下落时，不是从平台左侧跳下就是从右侧跳下。
我们用“第i个平台的左侧或右侧”表示jimmy的位置就行啦！
剩下的就是记忆化搜索或者dp了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=1005; int f[N][2]; struct pla { int x1,x2,h; }s[N]; int n,mx; bool cmp(pla a,pla b) {return a.h>b.h;} int dfs(int t,int p) { if(f[t][p]!=-1)return f[t][p]; f[t][p]=0x3f3f3f3f; bool flag=0; int q=0; if(p==0)q=s[t].x1; else q=s[t].x2; for(int i=t+1;i< =n;i++) if(s[t].h-s[i].h<=mx) if(s[i].x1<=q&&s[i].x2>=q) { f[t][p]=min(dfs(i,0)+abs(q-s[i].x1),dfs(i,1)+abs(q-s[i].x2))+s[t].h-s[i].h; flag=1;break; } if(!flag&&s[t].h< =mx)f[t][p]=s[t].h; return f[t][p]; } int main() { int cnt=0; scanf("%d",&cnt); while(cnt--) { scanf("%d%d%d%d",&n,&s[0].x1,&s[0].h,&mx);s[0].x2=s[0].x1; for(int i=1;i<=n;i++)scanf("%d%d%d",&s[i].x1,&s[i].x2,&s[i].h); sort(s,s+n+1,cmp); memset(f,-1,sizeof f); printf("%d\n",dfs(0,0)); } return 0; }
poj3666
给出一个数列，要求把这个数列a[i]改成非严格递增或者非严格递减的w[i],修改的代价为∑abs(w[i]-a[i]) 求最小代价
朴素的想法，f[i][j]表示前i个数，其中修改后最大的数为j的答案。
但是a[i]太大了，状态存不下。继续观察发现，修改后的数列里的数，可以全部都在原数列中找到。
什么意思呢？就是每次修改，可以理解为将a[i]变为a[j]，获得abs(a[j]-a[i])的代价。
这样一来就好办了，状态存下了，考虑转移
f[i][j]=abs(a[j]-a[i])+min(f[i-1][k]) 总体复杂度O(N^3) 不行。
观察到min(f[i-1][k])可以提前被算出，利用一个辅助数组完成转移。
mx[j]=min(f[i-1][k]) f[i][j]=abs(w[j]-a[i])+mx[j] 这里要dp两遍，一遍递增一遍递减，w[j]一遍排序成递增，一遍排序成递减。
这道题体现了”观察”并减少状态表示复杂度，以及利用辅助数组进行优化来减少转移复杂度。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<queue> using namespace std; const int N=2005; int f[N][N];//前i个数字 其中最大/最小值为w[j] int w[N],mx[N],mn[N],n,a[N]; bool cmp(int a,int b) {return a>b;} int up() { // w 从小到大 sort(w+1,w+n+1); memset(f,0x7f,sizeof f); for(int i=1;i< =n;i++) { for(int j=1;j<=n;j++) { f[i][j]=abs(w[j]-a[i])+mx[j]; } memset(mx,0x7f,sizeof mx); for(int j=1;j<=n;j++) mx[j]=min(mx[j-1],f[i][j]); } int ans=0x7fffffff; for(int i=1;i<=n;i++) ans=min(ans,f[n][i]); return ans; } int down() { sort(w+1,w+n+1,cmp); memset(f,0x7f,sizeof f); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { f[i][j]=abs(w[j]-a[i])+mn[j]; } memset(mn,0x7f,sizeof mn); for(int j=1;j<=n;j++) mn[j]=min(mn[j-1],f[i][j]); } int ans=0x7fffffff; for(int i=1;i<=n;i++) ans=min(ans,f[n][i]); return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),w[i]=a[i]; printf("%d\n",min(up(),down())); return 0; }