【HDOJ】1244 Max Sum Plus Plus Plus

6429 단어
이 문제는 줄곧 wa였는데, 알고 보니 내가 JUDGE를 잘못 썼기 때문이었구나. 그래, 오후 내내 찍었는데도 검사하지 못했다.물DP야.
 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 using namespace std;
 7 
 8 #define MAXN 1020
 9 #define MAXM 35
10 #define INF 0xfffff
11 
12 int dp[MAXM][MAXN];
13 int l[MAXM];
14 int sums[MAXN];
15 
16 int main() {
17     int n, m, sum;
18     int i, j, k, tmp;
19 
20 #ifndef ONLINE_JUDGE
21     freopen("data.in", "r", stdin);
22     freopen("data.out", "w", stdout);
23 #endif
24 
25     while (scanf("%d",&n)!=EOF && n) {
26         scanf("%d", &m);
27         for (i=1; i<=m; ++i)
28             scanf("%d", &l[i]);
29         sums[0] = 0;
30         for (i=1; i<=n; ++i) {
31             scanf("%d", &tmp);
32             sums[i] = sums[i-1] + tmp;
33         }
34         sum = 0;
35         memset(dp, 0, sizeof(dp));
36         for (i=m; i>0; --i) {
37             sum += l[i];
38             for (j=n-sum+1; j>0; --j) {
39                 dp[i][j] = max( dp[i][j+1], dp[i+1][j+l[i]]+(sums[j+l[i]-1]-sums[j-1]) );
40             }
41         }
42         printf("%d
", dp[1][1]); 43 } 44 45 return 0; 46 }

 
전재 대상:https://www.cnblogs.com/bombe1013/p/4087465.html

좋은 웹페이지 즐겨찾기