302 条题解
-
-2WBS LV 8 @ 2017-08-10 22:06:20
var
a:array[1..1000] of longint;
i,j,n,t,t1,t2,m:longint;
begin
readln(t,m);
fillchar(a,sizeof(j),0);
for i:=1 to m do
begin
readln(t1,t2);
for j:=t-t1 downto 0 do if a[j]+t2>a[j+t1] then a[j+t1]:=a[j]+t2;
end;
writeln(a[t]);
end. -
-22017-07-08 19:48:25@
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int main(){ int t, m; cin >> t >> m; int time[m + 1]; int value[m + 1]; for (int i = 1; i <= m; i++){ cin >> time[i] >> value[i]; } int dp[m + 1][t + 1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= m; i++){ for (int j = 0; j <= t; j++){ if (j - time[i] >= 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i]] + value[i]); else dp[i][j] = dp[i - 1][j]; } } cout << dp[m][t] << endl; return 0; }