AOJ 0573 - Night Market

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0573

解法

dp[i][j] = 時刻 j に i 番目の店にいるときの満足度の最大値

という DP 表を

dp[i][j] = max { dp[i-1][j - B[i]] + A[i]  if (S <= j - B[i] || j <= S) }

と埋める。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, T, S;
 8   scanf("%d %d %d", &N, &T, &S);
 9   static int as[3001], bs[3001];
10   for (int i = 1; i <= N; i++) {
11     scanf("%d %d", &as[i], &bs[i]);
12   }
13 
14   static int dp[3001][3001];
15   int ans = 0;
16   for (int i = 1; i <= N; i++) {
17     for (int j = 1; j <= T; j++) {
18       dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
19       const int beg = j-bs[i];
20       if (beg >= 0 && (S <= beg || j <= S)) {
21         dp[i][j] = max(dp[i][j], dp[i-1][beg] + as[i]);
22       }
23       ans = max(ans, dp[i][j]);
24     }
25   }
26   printf("%d\n", ans);
27   return 0;
28 }