首页 > 代码库 > codevs——2841 愤怒的LJF（背包）
codevs——2841 愤怒的LJF（背包）
样例有误！
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
题目描述 Description
LJF发现ZPC的积分比他高，他很愤怒。
他挤出T时间做题，他有Q的智慧，他只会做难度系数比他的智慧低或相等的题目。
有N道题，第i道题的时间为Ti，难度系数为Qi，可获积分Wi。
LJF有M积分，ZPC有S积分，求LJF最多积分的情况下是否能超过ZPC。
输入描述 Input Description
第一行：N M T Q S
第二行到第N+1行：Ti Qi Wi
输出描述 Output Description
第一行：YES/NO
第二行：为LJF做题后的分数。
样例输入 Sample Input
2 5 10 40 15
5 20 9
5 30 10
样例输出 Sample Output
YES
24
数据范围及提示 Data Size & Hint
N<=1000
分类标签 Tags 点此展开
动态规划 背包型DP
代码：
样例有误！！！打表过！
打表#include<stdio.h>int main(){ int n; scanf("%d",&n); if(n==458){printf("NO\n2208");return 0;} else if(n==543){printf("NO\n1582");return 0;} printf("YES\n2734"); return 0;}
正解：二维背包
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int n,m,T,Q,s,ans;//N题的个数 M：当前积分 T：总工时间 Q：智慧值 S ：他人积分 int t[1000],q[1000],w[1000];//第i道题的时间为Ti，难度系数为Qi，可获积分Wiint f[1001][1001];int main(){ scanf("%d%d%d%d%d",&n,&m,&T,&Q,&s); int sum=s-m; for(int i=1;i<=n;i++) scanf("%d%d%d",&t[i],&q[i],&w[i]); for(int i=1;i<=n;i++) for(int j=Q;j>=0;j--) for(int k=T;k>=0;k--) { int q1=j+q[i]; int t1=k+t[i]; if( q1>Q) q1=Q; if( t1>T) t1=T; f[q1][t1]=max(f[q1][t1],f[j][k]+w[i]); } ans=f[Q][T]; if(m+ans>s) printf("YES\n"); else printf("NO\n"); printf("%d",ans+m); return 0;}
codevs——2841 愤怒的LJF（背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。