#include<stdio.h>
#include<stdlib.h>
typedef struct Holl{
int time;
int value;
}Holl;
Holl* hollCaoyao(int num){
Holl* holl = (Holl*)malloc(sizeof(Holl)*(num+1));
for(int i = 1; i <= num; i++){
int time, value;
scanf("%d %d", &time, &value);
holl[i].time = time;
holl[i].value = value;
}
holl[0].time = 0;
holl[0].value = 0;
return holl;
}
int main()
{
int T,M;
scanf("%d %d", &T, &M);
Holl* holl = hollCaoyao(M);
int** dp = (int**)malloc(sizeof(int*)*(M+1));
for(int i = 0; i <= M; i++){
dp[i] = (int*)malloc(sizeof(int)*(T+1));
}
for(int i = 0; i <= M; i++){
for(int j = 0; j <= T; j++){
dp[i][j] = 0;
}
}
for(int i = 1; i <= M; i++){
for(int j = 1; j <= T; j++){
if(holl[i].time <= j){
if((holl[i].value+dp[i-1][j-holl[i].time])>dp[i-1][j]){
dp[i][j] = holl[i].value+dp[i-1][j-holl[i].time];
}
else{
dp[i][j] = dp[i-1][j];
}
}
else{
dp[i][j] = dp[i-1][j];
}
}
}
int max = 0;
for(int i = 0; i <= M; i++){
for(int j = 0; j <= T; j++){
//printf("%d ", dp[i][j]);
if(max<dp[i][j]){
max = dp[i][j];
}
}
//putchar('\n');
}
printf("%d", max);
return 0;
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:766 |
Tom数 (C++代码)浏览:869 |
输出正反三角形 (C语言代码)浏览:860 |
【亲和数】 (C语言代码)浏览:541 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:606 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:1292 |
WU-拆分位数 (C++代码)浏览:819 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:750 |
蓝桥杯历届试题-翻硬币 (C++代码)浏览:955 |
淘淘的名单 (C语言代码)浏览:1309 |