C++动态规划超详细总结-创新互联

看到这道题，大家可能毫无头绪（做题时不要损坏设备）

首先，田忌拥有比赛的“主动权”，因为他可以根据齐王出的马来出马。可以假设齐王出马的顺序是从强到弱，那么田忌出马应该是最强或最弱。用 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 种纪念品的价格。

输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

6 1 100
50
20
25
20
25
50

305

3 3 100
10 20 15
15 17 13
15 25 16

217

【输入输出样例 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元起，快前往官网查看详情吧