首页 > 其他分享 >P5662 [CSP-J2019] 纪念品

P5662 [CSP-J2019] 纪念品

时间:2024-05-24 21:08:55浏览次数:15  
标签:P5662 int J2019 CSP dp 105

原题链接

题解

定义 \(dp[i]\) 为今天有 \(i\) 元钱花时,明天卖能纯赚多少钱(这里有一个递归的思想,不需要考虑 \(dp[k-a[i][j]]\) 能否买得起今天的产品)
如果 \(dp[i-1]=k\) 那么 \(dp[i]\geq k\) ,所以存在一个 \(i\) 使得钱全部花完然后赚 \(k\) 元

code

#include<bits/stdc++.h>
using namespace std;
int dp[10005]={0};
int a[105][105];
int main()
{
    int t,n,m;
    cin>>t>>n>>m;

    for(int i=1;i<=t;i++)
    {
        for(int j=1;j<=n;j++) cin>>a[i][j];
    }

    int maxs=m;
    for(int i=1;i<t;i++)
    {
        memset(dp,0,sizeof dp);
        int add=0;
        for(int j=1;j<=n;j++)
        {
            for(int k=a[i][j];k<=maxs;k++)
            {
                dp[k]=max(dp[k],dp[k-a[i][j]]+a[i+1][j]-a[i][j]);
                add=max(add,dp[k]);
            }
        }
        maxs+=add;
    }

    cout<<maxs;
    return 0;
}

标签:P5662,int,J2019,CSP,dp,105
From: https://www.cnblogs.com/pure4knowledge/p/18211663

相关文章

  • mx 五月 csp-j
    T1考虑只有第二种操作。显然可以维护\(a_i\)代表当前序列的第\(i\)个数是什么。观察到变换只和\(k\%3\)的值有关。对于第一种操作,显然可以令\(k\leftarrowk\%n\)。观察到这种变换将整个序列视为一个环更方便一点,于是维护变换后第一个数的下标是多少。输出时按照环的......
  • CSP历年复赛题-P1061 [NOIP2006 普及组] Jam 的计数法
    原题链接:https://www.luogu.com.cn/problem/P1061题意解读:从编号s~t的字母从挑w个,组成一种特殊的数字,数字里字母都是升序的,给定初始数字,要计算后5个。解题思路:1、模拟法模拟样例:2105有效字母范围:b,c,d,e,f,g,h,i,j 初始值:bdfij要计算bdfij的下一个,采取如下步骤......
  • CCF/CSP认证-第一次-命令行选项
    1.问题1.1命令行选项请你写一个命令行分析程序,用以分析给定的命令行里包含哪些选项。每个命令行由若干个字符串组成,它们之间恰好由一个空格分隔。这些字符串中的第一个为该命令行工具的名字,由小写字母组成,你的程序不用对它进行处理。在工具名字之后可能会包含若干选项,然后......
  • CSP历年复赛题-P1046 [NOIP2005 普及组] 陶陶摘苹果
    原题链接:https://www.luogu.com.cn/problem/P1046题意解读:30+伸手的高度,能够得着几个苹果。解题思路:直接模拟。100分代码:#include<bits/stdc++.h>usingnamespacestd;inta[15],h,ans;intmain(){for(inti=1;i<=10;i++)cin>>a[i];cin>>h;......
  • CSP历年复赛题-P1087 [NOIP2004 普及组] FBI 树
    原题链接:https://www.luogu.com.cn/problem/P1087题意解读:字符串作为根,左边一半作为左子树,右边一半作为右子树,递归构造数,并按FBI规则输出后续遍历结果。解题思路:按照题意,通过dfs来构造树,对于字符串str,提取左边一半递归构造左子树,提取右边一半递归构造右子树,前提是字符串长度>1......
  • CSP历年复赛题-P1085 [NOIP2004 普及组] 不高兴的津津
    原题链接:https://www.luogu.com.cn/problem/P1085题意解读:找到两数之和大于8且两数之和最大值的位置解题思路:不多说,送分题,直接模拟法即可100分代码:#include<bits/stdc++.h>usingnamespacestd;inta,b;intmaxx,maxn;intmain(){for(inti=1;i<=7;i++)......
  • CSP历年复赛题-P1044 [NOIP2003 普及组] 栈
    原题链接:https://www.luogu.com.cn/problem/P1044题意解读:一组数入栈、出栈的方案数,如果了解卡特兰数,此题可以秒杀;如果不了解,也可以通过递归或者递推来解决;最次,可以通过DFS暴搜出方案数,当然对于n个数,一共有n次入栈、n次出栈,一共2n次,每次要么入栈要么出栈,总搜索次数在22n规模,n最......
  • CSP历年复赛题-P1045 [NOIP2003 普及组] 麦森数
    原题链接:https://www.luogu.com.cn/problem/P1045题意解读:要计算2p-1的位数和最后500位,实际上只需要计算2p,两者位数一致,前者比后者个位减1即可,且个位肯定不会是0,比较容易处理。解题思路:如果直接采用高精度乘法计算2p,p最大3.1*106,高精度所用数组最长大概9*105,一共最多计算3.......
  • CSP历年复赛题-P1043 [NOIP2003 普及组] 数字游戏
    原题链接:https://www.luogu.com.cn/problem/P1043题意解读:将n个环形数分成任意m组,组内求和再%10、负数转正,组间相乘,求所有分组方案中得到结果的最小值和最大值。解题思路:比赛题的首要目的是上分!此题一看就是DP,但是苦苦思索了半天,想不清楚状态表示,那么可以换换策略,先暴力得分再......
  • CSP历年复赛题-P1037 [NOIP2002 普及组] 产生数
    原题链接:https://www.luogu.com.cn/problem/P1037题意解读:一个长整数,有若干数字替换规则,计算可以转换成多少种不同的整数。解题思路:看题之后,第一感觉,是用DFS:1、用字符串存储整数2、用领接表存储数字替换规则,因为一个数字可以替换成多个其他数字3、在dfs中,枚举字符串每个数字......