Problem 1043 - Qinz大牛的烦恼

你的名字 2021-12-22 07:19 154阅读 0赞

题目地址：[http://acm.xidian.edu.cn/land/problem/detail?problem\_id=1043][http_acm.xidian.edu.cn_land_problem_detail_problem_id_1043]

经典0-1背包。这是我写的第一个背包。利用dp思想。f\[i\]为容量为i的背包所放最大价值。核心代码是f\[i\]=max\{  f\[i\]  ,  f \[ i - t \[ i \] \] + s \[ i \]  \};下面是AC代码。还需要继续学习。

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<stdlib.h>
     4 int f[500],s[500],t[500];
     5 int max(int a,int b) {
        return a>b?a:b;}
     6 int main()
     7 {
     8     int T,n,m,i,j;
     9     scanf("%d",&T);
    10     while(T--)
    11     {
    12         memset(f,0,sizeof(f));
    13         memset(s,0,sizeof(s));
    14         memset(t,0,sizeof(t));
    15         scanf("%d%d",&n,&m);
    16         for(i=1;i<=n;i++)
    17             scanf("%d%d",&s[i],&t[i]);
    18         for(i=1;i<=n;i++)
    19             for(j=m;j>=t[i];j--)
    20                 f[j]=max(f[j],f[j-t[i]]+s[i]);
    21         printf("%d\n",f[m]);
    22     }
    23     return 0;
    24 }

转载于:https://www.cnblogs.com/hjf007/p/3266338.html

[http_acm.xidian.edu.cn_land_problem_detail_problem_id_1043]: http://acm.xidian.edu.cn/land/problem/detail?problem_id=1043

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关主持人的烦恼【牛客】

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld 题目描述一

川长思鸟来/ 2023年09月29日 08:27/ 0 赞/ 7 阅读

相关程序员10大烦恼

此处有雷区，闲杂人等请勿靠近嘿嘿 ![a33f1d0db098123be36e9ba437dc2b18.png][] 1、困哥，你那个

今天药忘吃喽~/ 2022年12月27日 00:19/ 0 赞/ 176 阅读

相关 1043 鸡蛋掉落

Description 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不

ゝ一世哀愁。/ 2022年09月12日 03:50/ 0 赞/ 158 阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 214 阅读

相关大牛的资料

[http://mt.sohu.com/20160407/n443539407.shtml][http_mt.sohu.com_20160407_n443539407.shtm

我会带着你远行/ 2022年07月15日 14:07/ 0 赞/ 177 阅读

相关 PAT乙级1043

1043 输出PATest （20 分）给定一个长度不超过 104 的、仅由英文字母构成的字符串。请将字符重新调整顺序，按 `PATestPATest....` 这样的顺序

╰半夏微凉°/ 2022年05月06日 11:00/ 0 赞/ 465 阅读

相关 PAT A1043

![clipboard.png][] 简单的不用考虑平衡的二叉查询树；我发现我有读题障碍症。。。 include<iostream> include

迷南。/ 2022年03月07日 03:46/ 0 赞/ 196 阅读

相关 ☆1043

BST的插入操作 void Insert(node &root, int data){//因为要更改root的值；&：别名。 if(root==NULL){

红太狼/ 2022年01月06日 14:27/ 0 赞/ 246 阅读

相关 Problem 1043 - Qinz大牛的烦恼

题目地址：[http://acm.xidian.edu.cn/land/problem/detail?problem\_id=1043][http_acm.xidian.edu

你的名字/ 2021年12月22日 07:19/ 0 赞/ 155 阅读

相关 hdu 1043 Eight

Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

我不是女神ヾ/ 2021年09月29日 06:08/ 0 赞/ 233 阅读