c++11/c++98动态规划入门第5课,经典DP问题 --- 区间

这篇具有很好参考价值的文章主要介绍了c++11/c++98动态规划入门第5课,经典DP问题 --- 区间。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

c++11/c++98动态规划入门第5课,经典DP问题 --- 区间,动态规划,算法,c++

第1题     取数问题 查看测评数据信息

    有一排N个数,你和小明2个人玩游戏,每个人轮流从2端取数,每次可以从左或右取,不能从中间取。你取的所有的数的和是你的得分,小明取的所有的数的和是小明的得分。如果你先取,你最多比小明多得多少分?

输入格式

  第一行:一个整数n,范围在[0, 100]。

  第二行:n个整数,每个数范围在[1, 10000]。

输出格式

  小明足够聪明时,你最多多得的分数。

输入/输出例子1

输入:

  4

  3 2 9 1

输出:

  9

样例解释:          

第1轮你取3;

第2轮他取2;

第3轮你取9;

第4轮他取1;

(3+9)-(2+1) = 9

样例解释

代码:

#include<bits/stdc++.h>
using namespace std;
int n,f[105][105],a[105],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],f[i][i]=a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j+i<=n;j++)
            f[j][j+i]=max(-f[j+1][j+i]+a[j],-f[j][i+j-1]+a[i+j]);        
    cout<<f[1][n];
    return 0;
}

c++11/c++98动态规划入门第5课,经典DP问题 --- 区间,动态规划,算法,c++

第1题     数字(number) 查看测评数据信息

有n个数字(0到99)排成一行,每一次可以将相邻的两个数字相加并对100取模(即除以100的余数),将结果取代之前的两个数,一次操作的花费为两个数字相乘。经过n-1次操作后剩下一个数,问剩下一个数时总花费的最小值。

输入格式

有若干组数据,每组数据第一行为一个正整数n(n<=100)表示数字的个数。

第二行为n个正整数(0到99)

输出格式

每组数据对应的最小花费。

输入/输出例子1

输入:

2

18 19

3

40 60 20

 

输出:

342

2400

样例解释

对于第二组数据有两种方案:

1、  先将(40和60)相加得0,再将0 和20相加得20,总花费为40*60+0*20=2400

2、  先将(60和20)相加得80,再将40和80相加得20,总花费为60*20+40*80=4400

显然第一种方案较好。

 

样例解释

代码:

#include<bits/stdc++.h>
using namespace std;
int n,a[105],f[105][105],d[105];
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i = 0;i <= 105;i++){
        	for(int j = 1;j <= 105;j++)
            f[i][j] = 1250000;
        }
        for(int i = 1;i <= 105;i++){
            d[i] = 0;
        }
        for(int i = 1;i <= n;i++){
            cin>>a[i];
            d[i] = d[i-1]+a[i];
            f[i][i] = 0;
        }
        for(int i = 2;i <= n;i++)
            for(int j = i;j <= n;j++){
                int lt = j-i+1;
                for(int k = lt;k < j;k++){
                    int x = (d[k]-d[lt-1])%100;
                    int y = (d[j]-d[k])%100;
                    f[lt][j]=min(f[lt][j],f[lt][k]+f[k+1][j]+x*y);
                }
            }
        cout<<f[1][n]<<endl;
    }
    return 0;
}
  • 测试
第1题     救灾 查看测评数据信息

为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买。请问:你用有限的资金最多能采购多少公斤粮食呢?

输入格式

输入数据首先包含一个正整数C,表示有C(C<=10)组测试数据,每组测试数据的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类,然后是m行数据,每行包含3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20),分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

输出格式

对于每组测试数据,请输出能够购买大米的最多重量,你可以假设经费买不光所有的大米,并且经费你可以不用完。每个数据的输出占一行。

输入/输出例子1

输入:

1

8 2

2 100 4

4 100 2

输出:

400

样例解释

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105],b[105],c[105];
int dp[105];
int n,m;   
int main()
{
    int C;
    scanf("%d",&C);
    while(C--)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d %d",&n,&m);
        for(int i=0; i<m; i++)
        {
            scanf("%d %d %d",&a[i],&b[i],&c[i]);
        }
        for(int i=0; i<m; i++)
        {
            for(int j=1; j<=c[i]; j++)
            {
                for(int k=n; k>=a[i]*j; k--)
                {
                    dp[k]=max(dp[k-a[i]]+b[i], dp[k]);
                }
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}
第3题     光盘 查看测评数据信息

有N张光盘,每张光盘有一个价钱,现在要从N张光盘中买M张,预算为L,每张光盘有一个快乐值,要求在不超过预算并且恰好买M张,使得快乐值总和最大。

输入格式

第一行为一个正整数T(1<=T<=5)表示测试数据个数

每组测试数据第一行为三个正整数N(N<=100),M(M<=N),L(L<=1000)

接下来的N行每行有两个正整数,分别是光盘的价钱与快乐值。

输出格式

每组数据对应的最大快乐值总和(保证小于2^31)。若无解则输出0.

输入/输出例子1

输入:

1

3 2 10

11 100

1 2

9 1

输出:

3

样例解释

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 1010;
const int INF = 1 << 31;
struct Movie
{
    int t,v;
};
Movie movie[MAXN];
int dp[MAXN][MAXN];
int n,m,l;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&l);
        for(int i = 1;i <= m;i++)
            for(int j = 0;j <= l;j++)
                dp[j][i] = -INF;
        for(int j = 0;j <= l;j++)
            dp[j][0] = 0;
        for(int i = 1;i <= n;i++)
            scanf("%d%d",&movie[i].t,&movie[i].v);
        for(int i = 1;i <= n;i++)
            for(int j = l;j >= movie[i].t;j--)
            for(int k = m;k >= 1;k--)
            dp[j][k] = max(dp[j][k],dp[j-movie[i].t][k-1]+movie[i].v);
        int ans = 0;
        for(int i = 1;i <= l;i++)
            if(dp[i][m] > ans)
            ans = dp[i][m];
        printf("%d\n",ans);
    }
    return 0;
}

总结:

状态:线性DP --?-- 区间DP

阶段:长度

阶段的方向:2种  ------ 取决于“子问题”文章来源地址https://www.toymoban.com/news/detail-653658.html

到了这里,关于c++11/c++98动态规划入门第5课,经典DP问题 --- 区间的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 区间dp(动态规划)

    动态规划(dp)是一种通过将问题分解为子问题,并利用已解决的子问题的解来求解原问题的方法。适用于具有重叠子问题和最优子结构性质的优化问题。通过定义状态和状态转移方程,动态规划可以在避免重复计算的同时找到问题的最优解,是一种高效的求解方法,常用于

    2024年02月15日
    浏览(41)
  • 动态规划——区间DP 学习笔记

    不含四边形不等式优化。 线性动态规划的局限性在于,它只能顺推或倒退,而不能有子区间依赖的问题。 区间动态规划是线性动态规划的扩展,它将问题划分为若干个子区间,并通过定义状态和状态转移方程来求解每个子区间的最优解,最终得到整个区间的最优解。 区间动

    2024年02月08日
    浏览(42)
  • 动态规划——区间dp [石子合并]

    动态规划(dp)是一种通过将问题分解为子问题,并利用已解决的子问题的解来求解原问题的方法。适用于具有重叠子问题和最优子结构性质的优化问题。通过定义状态和状态转移方程,动态规划可以在避免重复计算的同时找到问题的最优解,是一种高效的求解方法,常用于

    2024年02月12日
    浏览(46)
  • 动态规划系列 | 一文搞定区间DP

    区间 DP 可以用于解决一些涉及到区间合并或分割的问题。区间 DP 通常有以下三个特点: 合并(分割) :将两个或多个部分进行整合,或者反过来将一个区间分解成多个部分。 特征 :能将问题分解为能两两合并的形式。 求解 :对整个问题设最优解,枚举合并点,将问题分

    2024年02月02日
    浏览(47)
  • 石子合并(动态规划 区间DP)+详细注释

    原题链接   活动 - AcWing 题目 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相

    2024年02月16日
    浏览(39)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(52)
  • 11.动态规划:树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增(LCA)【灵神基础精讲】

    回溯和树形DP的区别(什么时候需要return结果?):对于回溯,通常是在「递」的过程中增量地构建答案,并在失败时能够回退,例如八皇后。对于递归,是把原问题分解为若干个相似的子问题,通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化,就

    2024年02月04日
    浏览(41)
  • 【动态规划 区间dp 位运算】100259. 划分数组得到最小的值之和

    动态规划 区间dp 位运算 给你两个数组 nums 和 andValues,长度分别为 n 和 m。 数组的 值 等于该数组的 最后一个 元素。 你需要将 nums 划分为 m 个 不相交的连续 子数组,对于第 ith 个子数组 [li, ri],子数组元素的按位AND运算结果等于 andValues[i],换句话说,对所有的 1 = i = m,n

    2024年04月15日
    浏览(32)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • 动态规划-经典dp(打家劫舍,股票等)

    1.1.1 爬楼梯  由于求的是组合数,我们将不同路径相加即可 dp定义: dp[i]为爬到第i阶楼梯的方法数; 转移方程: 初始化:  由于涉及到i-2和i-1,那么我们要从i=2开始遍历,因此要初始化dp[0] = 0,dp[1] = 1(根据定义) 遍历顺序: 从左往右  完整代码:  1.1.2 使用最小花费爬楼梯

    2024年01月19日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包