13518219792
首先来介绍一下动态规划，但我不想用过于官方的语言来介绍。动态规划是一种思想，它常用于最优解问题（即所有问题包括所有子问题的解为最优解），它有点像递推，是在已知问题的基础上解决其他问题。这种思想较为复杂，也是很多 OIer 的痛。
把一个问题拆分成很多小问题
找出最初的状态（即上文“在已知问题的基础上”的已知部分）
建立状态转移方程（即上文“解决其他问题”）
其实状态转移方程有点像找规律，通过前面的规律推出后面。
例题讲解我们先从最简单经典的跳台阶问题开始。
台阶问题 题目描述有 N 级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（1或2级），问到达第N级台阶有多少种不同方式。
输入格式两个正整数N，K。
输出格式一个正整数，为不同方式数。
样例 #1 样例输入 #15 28首先题目的意思就是 N 阶台阶，每次可以迈 1或2 阶，问有几种迈的方法。
这里我们不妨设一个函数
为结果。
每阶台阶可以向上走 1或2阶，那么第 N 阶台阶一定是从 N-1 或者 N-2 阶台阶来的，第 N-1 或 N-2 阶台阶也一定是从 N-3/N-2 或 N-3/N-4 来的，以此类推。
那么，状态转移方程为
dp[N]=dp[N-1]+dp[N-2]怎么样，是不是很简单？
难度提升！
代码#includeusing namespace std;
int m,dp[3],n;
int main(){
cin >>n;
for(int i=1;i<=n;i++){
cin >>m;
dp[0]=1;
dp[1]=1;
if(m<2) break;
for(int j=2;j 我国历史上有个著名的故事： 那是在2300年以前。齐国的大将军田忌喜欢赛马。他经常和齐王赛马。他和齐王都有三匹马：常规马，上级马，超级马。一共赛三局，每局的胜者可以从负者这里取得200银币。每匹马只能用一次。齐王的马好，同等级的马，齐王的总是比田忌的要好一点。于是每次和齐王赛马，田忌总会输600银币。
田忌很沮丧，直到他遇到了著名的军师――孙膑。田忌采用了孙膑的计策之后，三场比赛下来，轻松而优雅地赢了齐王200银币。这实在是个很简单的计策。由于齐王总是先出最好的马，再出次好的，所以田忌用常规马对齐王的超级马，用自己的超级马对齐王的上级马，用自己的上级马对齐王的常规马，以两胜一负的战绩赢得200银币。实在很简单。
如果不止三匹马怎么办？这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边，把齐王的马放右边。田忌的马A和齐王的B之间，如果田忌的马胜，则连一条权为200的边；如果平局，则连一条权为0的边；如果输，则连一条权为－200的边……如果你不会求最佳匹配，用最小费用大流也可以啊。 然而，赛马问题是一种特殊的二分图最佳匹配的问题，上面的算法过于先进了，简直是杀鸡用牛刀。现在，就请你设计一个简单的算法解决这个问题。
输入格式第一行一个整数n，表示他们各有几匹马（两人拥有的马的数目相同）。第二行n个整数，每个整数都代表田忌的某匹马的速度值(0<= 速度值<= 100)。第三行n个整数，描述齐王的马的速度值。两马相遇，根据速度值的大小就可以知道哪匹马会胜出。如果速度值相同，则和局，谁也不拿钱。
数据规模对于20%的数据，1<=N<=65；
对于40%的数据，1<=N<=250；
对于100%的数据，1<=N<=2000。
输出格式仅一行，一个整数，表示田忌大能得到多少银币。
样例 #1 样例输入 #13
92 83 71
95 87 74200这道题除了 DP ，还有简单的做法，我直接放代码，但为了学习 DP，我还是讲一下 DP 做法。
简单解法//田忌赛马
#include#include
using namespace std;
int n,qsp[2010],tsp[2010];
int main(){
cin>>n;
for(int i=0;i>tsp[i];
}
for(int i=0;i>qsp[i];
}
sort(qsp,qsp+n);
sort(tsp,tsp+n);
int tmin=0,tmax=n-1,qmin=0,qmax=n-1,jb=0;
for(int i=0;iqsp[qmin]){
jb+=200;
tmin++;
qmin++;
}
else if(tsp[tmax]>qsp[qmax]){
jb+=200;
tmax--;
qmax--;
}
else if(tsp[tmin] 这段代码大家应该能看懂，我不做讲解。
DP 做法看到这道题，大家可能毫无头绪（做题时不要损坏设备）
首先，田忌拥有比赛的“主动权”，因为他可以根据齐王出的马来出马。可以假设齐王出马的顺序是从强到弱，那么田忌出马应该是最强或最弱。用 f[i,j] 表示齐王出了 i 匹较强的马和田忌出了 j 匹较强的马。i-j 表示较弱的马比赛之后田忌获得的利益。
那么状态转移方程是
f[i][j]=max(f[i-1][j]+g[n-i+j+1][i],f[i-1][j-1]+g[j][i])其中g[i][j] 表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第 i 匹马和齐王的第 j 匹马赛跑所能取得的盈利，胜为 200 ，负为 −200 ，平为 0。
代码#include#include#include
using namespace std;
const int N=2001,INF=-2e+8;
int a[N],b[N],g[N][N],f[N];
bool Cmp(int n1,int n2) {return n1>n2;}
int main()
{
int n,Ans,i,j; scanf("%d",&n);
for (i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) scanf("%d",&b[i]);
sort(a+1,a+n+1,Cmp),sort(b+1,b+n+1,Cmp);
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
{
if (a[i]>b[j]) g[i][j]=200;
else if (a[i]==b[j]) g[i][j]=0;
else g[i][j]=-200;
}
for (i=1;i<=n;++i) f[i]=INF;
for (i=1;i<=n;++i)
{
f[i]=f[i-1]+g[i][i];
for (j=i-1;j>0;--j)
f[j]=max(f[j]+g[n-i+j+1][i],f[j-1]+g[j][i]);
f[0]=f[0]+g[n-i+1][i];
}
Ans=f[1];
for (i=2;i<=n;++i) Ans=max(Ans,f[i]);
printf("%d\n",Ans);
return 0;
} 怎么样，还能理解吗？
[ 真题 ] 纪念品动态规划的难度和精髓在于状态转移方程。 ——鲁迅（我没说过这句话）
接下来这道题会让大家知道什么是真正的状态转移方程。
题目描述小伟突然获得一种超能力，他知道未来 T 天 N 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。
每天，小伟可以进行以下两种交易无限次：
1. 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
2. 卖出持有的任意一个纪念品，以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
T 天之后，小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。
小伟现在有 M 枚金币，他想要在超能力消失后拥有尽可能多的金币。
输入格式第一行包含三个正整数 T, N, M，相邻两数之间以一个空格分开，分别代表未来天数 T，纪念品数量 N，小伟现在拥有的金币数量 M。
接下来 T 行，每行包含 N 个正整数，相邻两数之间以一个空格分隔。第 i 行的 N 个正整数分别为 P_{i,1}，P_{i,2},……,P_{i,N}，其中 P_{i,j} 表示第 i 天第 j 种纪念品的价格。
输出格式输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。
样例 #1 样例输入 #16 1 100
50
20
25
20
25
503053 3 100
10 20 15
15 17 13
15 25 16217【输入输出样例 1 说明】
最佳策略是：
第二天花光所有 100 枚金币买入 5 个纪念品 1；
第三天卖出 5 个纪念品 1，获得金币 125 枚；
第四天买入 6 个纪念品 1，剩余 5 枚金币；
第六天必须卖出所有纪念品换回 300 枚金币，第四天剩余 5 枚金币,共 305 枚金币。
超能力消失后，小伟最多拥有 305 枚金币。
【输入输出样例 2 说明】
最佳策略是：
第一天花光所有金币买入 10 个纪念品 1；
第二天卖出全部纪念品 1 得到 150 枚金币并买入 8 个纪念品 2 和 1 个纪念品 3，剩余 1 枚金币；
第三天必须卖出所有纪念品换回216 枚金币，第二天剩余1枚金币，共 217 枚金币。
超能力消失后，小伟最多拥有 217 枚金币。
纪念品问题的解法
思路这道题其实是动态规划和完全背包问题的结合。
我们进行 t−1 轮完全背包:
把今天手里的钱当做背包的容量，
把商品今天的价格当成它的消耗,
把商品明天的价格当做它的价值，
每一天结束后把总钱数加上今天赚的钱，直接写背包模板即可。
另： 在这道题中，我们可以把商品和钱看成同样的东西，因为题目中说了：可以当天买当天卖，所以不必考虑跨天的买卖，只需考虑当天的即可，这满足动态规划对于最优化原理和无后效性的要求，可以大胆地购买。
除第一天只有购入过程、最后一天只有售出过程外，每天都有售出与购入两个过程。两个过程互不干扰。
为获得更多的“资金”，不妨令每日的售出过程先于购入过程。
每天的购入过程与次日的售出过程（差价）构成一次完全背包。或者说，完全背包是在“第 X.5 天”进行的。
定义：
f[i]为用 i 元钱去购买商品所能盈利的大值（不含成本）
状态转移方程： f[j]=max(f[j],f[j−price[i][k]]+price[i][k+1]−price[i][k]);
代码#include#includeusing namespace std;
const int N = 101;
const int M = 10001;
int n, m, t, price[N][N], f[M];
int main()
{
cin >>t >>n >>m;
for(int i = 1; i<= t; i++)
for(int j = 1; j<= n; j++)
cin >>price[j][i];
//读入每种商品每天的价格
for(int k = 1; k< t; k++)
{
memset(f, 0, sizeof f);//每轮开始前都要制零
for(int i = 1; i<= n; i++)
for(int j = price[i][k]; j<= m; j++)//完全背包,正着循环
f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);
m += f[m];//加上盈利的钱，进入下一轮买卖
}
cout<< m;
return 0;
} 这样就好了（
最后这篇博客到这里也就结束了，今天主要是介绍了《简单》的动态规划问题（bushi，题目提交地址可以看我的 OJ。（
拜拜~~
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
