知识储备：dp入门。
好了，完成了dp入门，我们可以做一些稍微不是那么裸的题了。
dp基础，主要是做题，只有练习才能彻底掌握。
洛谷P1417 烹调方案
分析：由于时间的先后会对结果有影响，所以c[i]*b[j]>c[j]*b[i]为条件排序，然后再01背包。
洛谷P1387 最大正方形
分析：用dp[i][j]来表示以a[i][j]（正方形数组）为右下角最后一个数的正方形边长，a数组可以直接用dp数组代替掉。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=;
int dp[maxn][maxn];
int min_a(int a,int b,int c)
{
return min(min(a,b),min(b,c));
}
int main()
{
int n,m,ans=-;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&dp[i][j]);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(dp[i][j]>=)
{
dp[i][j]=min_a(dp[i-][j],dp[i-][j-],dp[i][j-])+;
}
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
ans=max(ans,dp[i][j]);
}
printf("%d",ans);
return ;
}
洛谷P1006 传纸条
分析：拿到题我不假思索地写了一份 单次最大好心值+dfs路径还原标记+单次最大好心值，然而发现，第一次最大好心值的路线把第二次堵死了。。。
好吧，正解是双线程，dp[k][i][j]表示走了k步，两份纸条横坐标分别是i,j时的好心最大值。
安利一发别人博客，讲得很透彻：http://www.cnblogs.com/OIerShawnZhou/p/7492555.html
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=;
int dp[*maxn][maxn][maxn],a[maxn][maxn],go[maxn][maxn];
//dp[k][i][j]走了k步，两份纸条横坐标分别是i,j时的好心最大值
int max_a(int a,int b,int c,int d)
{
return max(max(a,b),max(c,d));
}
int main()
{
int m,n,ans=;
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]);
for(int k=;k<n+m;k++)//步数
{
for(int i=;i<=k;i++)
{
for(int j=;j<=k;j++)
{
dp[k][i][j]=max_a(dp[k-][i][j],dp[k-][i][j-],dp[k-][i-][j],dp[k-][i-][j-])+a[i][k-i+]+a[j][k-j+];
if(i==j) dp[k][i][j]-=a[i][k-i+];//重复了
}
}
}
printf("%d",dp[n+m-][m][m]);
return ;
}
洛谷P1282 多米诺骨牌
分析：拿到题有点懵，但仔细想想，这好像也算是01背包，可以把翻转每个骨牌得到的点数差看做一件物品（记住，点数不带绝对值），但会出现数组下标为负数的情况，这个时候把 N 看做为0，N-1就是-1，N+1就是1
dp[i][j]：前i张牌使得上一行点数之和为j的最小方法数
普通版：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=;
const int N=maxn*,INF=;
int dp[maxn][*N],a[maxn],b[maxn];//dp[i][j]：前i张牌使得上一行点数之和为j的最小方法数
int main()
{
int n,minnum=INF,k=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
for(int i=;i<maxn;i++)
for(int j=;j<*N;j++)
dp[i][j]=INF;
dp[][N]=;
for(int i=;i<=n;i++)
{
for(int j=-N;j<=N;j++)
{
int dis=a[i]-b[i];//有正有负，故而开数组要开2*N,下面j+N同理
dp[i][j+N]=min(dp[i-][j+dis+N]+,dp[i-][j-dis+N]);//翻或不翻
}
}
for(int i=;i<=N;i++)
{
minnum=min(dp[n][N-i],dp[n][N+i]);
if(minnum!=INF)
{
printf("%d",minnum);
return ;
}
}
return ;
}
滚动数组优化：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=;
const int N=maxn*,INF=;
int dp[][*N],a[maxn],b[maxn];//dp[i][j]：前i张牌使得上一行点数之和为j的最小方法数
int main()
{
int n,minnum=INF,k=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
for(int i=;i<;i++)
for(int j=;j<*N;j++)
dp[i][j]=INF;
dp[][N]=;
for(int i=;i<=n;i++)
{
for(int j=-N;j<=N;j++)
{
int dis=a[i]-b[i];//有正有负，故而开数组要开2*N,下面j+N同理
dp[i&][j+N]=min(dp[(i-)&][j+dis+N]+,dp[(i-)&][j-dis+N]);//翻或不翻
}
}
for(int i=;i<=N;i++)
{
minnum=min(dp[n&][N-i],dp[n&][N+i]);
if(minnum!=INF)
{
printf("%d",minnum);
return ;
}
}
return ;
}
洛谷P1880 石子合并
分析：曾经的noi系列。石子合并问题分好几种情况。
这题是环形的，且只能合并相邻的两堆，那么我们把石子数组展开，如[1,2,3,4,5] -> [1,2,3,4,5,1,2,3,4,5]，这样进行处理，就能将环形转换成直线。
转换完之后，就可以用dp做了，dp的解释详见代码。这题数据过得去，时间是 O(n3) 不然要用平行四边形优化。
安利一发acdreamer的博客，把石子合并问题讲的很清楚http://blog.csdn.net/acdreamers/article/details/18039073
#include <cstdio>
#include <algorithm>
using namespace std;
int sum[],mins[][],maxs[][],s[][];//dp[i][j]=i~j的最大得分
int main()
{
int a,n,minnum=,maxnum=-minnum;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&sum[i]);
sum[i+n]=sum[i];
s[i][i]=i;
s[i*][i*]=i;
}
for(int i=;i<=*n;i++) sum[i]+=sum[i-]; //前缀和
for(int l=;l<=n;l++)//区间长度
{
for(int i=;i+l<=*n;i++)//开始的端点
{ int j=i+l;//结束的端点
maxs[i][j]=-;mins[i][j]=-*maxs[i][j];
for(int k=i;k<j;k++)
{
maxs[i][j]=max(maxs[i][j],maxs[i][k]+maxs[k+][j]+sum[j]-sum[i-]);
mins[i][j]=min(mins[i][j],mins[i][k]+mins[k+][j]+sum[j]-sum[i-]);
}
}
}
for(int i=;i<=n;i++)//因为是环形的，可从任意两堆间分开，所以需要枚举一遍起点从1~n
{
maxnum=max(maxs[i][i+n-],maxnum);
minnum=min(mins[i][i+n-],minnum);
}
printf("%d\n%d",minnum,maxnum);
return ;
}
洛谷P1108 低价购买
分析：第一问还是很简单的，求最长下降子序列。第二问要计算方案数量，还要判重。
用t[i]表示前i个股票的不同方案个数，可以得出，如果存在dp[j]==dp[i] && a[j]==a[i]方案就是重复的，所以就把t[i]赋为0，如果f[i]==f[j]+1，那么i可以从j转移，所以t[i]+=t[j]。最后统计和即可。
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[],a[],t[];//t，计算出现次数的dp
int main()
{
int ans=-,n,k=,res=;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
dp[i]=;
for(int j=;j<i;j++)
{
if(a[j]>a[i]) dp[i]=max(dp[i],dp[j]+);
}
ans=max(ans,dp[i]);
}
for(int i=;i<=n;i++)
{
if(dp[i]==) t[i]=;//如果无法转移则为1
for(int j=;j<i;j++)
{
if(dp[j]==dp[i]- && a[i]<a[j])//判前继 判可以为下一个数
{
t[i]+=t[j];//转移
}
else if(dp[i]==dp[j]&&a[i]==a[j]) t[j]=;//判重
}
}
for(int i=;i<=n;i++)
{
if(dp[i]==ans) res+=t[i];
}
printf("%d %d",ans,res);
return ;
}