Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N).?

You should output S.? 這兩道題的題目的題目大意如上，對于輸入的n個數，求出最大的S 這是一個簡單的DP題，開兩個數組，DP[i][0],DP[i][1]; 其中DP[i][0]表示的是從0～i中連續子串的最大和 DP[i][1]表示i～n-1中連續子串的最大和 則題目就變成求max{DP[i][0]+DP[i+1][1]}

參考代碼：

poj2479

1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8 int a[50005];
9 int dp[50005][2];
10 int i ;
11 int main()
12 {
13 int t ;
14 scanf("%d",&t);
15 while ( t -- )
16 {
17 int n ;
18 int sum=0;
19 scanf("%d",&n);
20 for ( i = 0 ; i < n ; i ++ )
21 {
22 scanf ("%d", &a[i]) ;
23 if ( i )
24 {
25 sum = max(sum+a[i],a[i]);
26 dp[i][0]=max(sum,dp[i-1][0]);
27 }
28 else
29 dp[i][0]=sum=a[i];
30 }
31 for ( i = n -1 ; i>=0 ; i -- )
32 {
33 if ( i != ( n - 1 ) )
34 {
35 sum = max(sum + a[i] , a[i]);
36 dp[i][1]=max(sum,dp[i+1][1]);
37 }
38 else
39 dp[i][1]=sum=a[i];
40 }
41 sum = -(1<<30) ;
42 for ( i = 0 ; i < n - 1 ; i ++ )
43 sum = max ( sum , dp[i][0]+dp[i+1][1] );
44 printf("%d\n",sum);
45 }
46 return 0;
47 }

　　poj2593

1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8 int a[100005];
9 int dp[100005][2];
10 int i ;
11 int main()
12 {
13 int n ;
14 while ( scanf("%d",&n) , n )
15 {
16
17 int sum=0;
18 for ( i = 0 ; i < n ; i ++ )
19 {
20 scanf ("%d", &a[i]) ;
21 if ( i )
22 {
23 sum = max(sum+a[i],a[i]);
24 dp[i][0]=max(sum,dp[i-1][0]);
25 }
26 else
27 dp[i][0]=sum=a[i];
28 }
29 for ( i = n -1 ; i>=0 ; i -- )
30 {
31 if ( i != ( n - 1 ) )
32 {
33 sum = max(sum + a[i] , a[i]);
34 dp[i][1]=max(sum,dp[i+1][1]);
35 }
36 else
37 dp[i][1]=sum=a[i];
38 }
39 sum = -(1<<30) ;
40 for ( i = 0 ; i < n - 1 ; i ++ )
41 sum = max ( sum , dp[i][0]+dp[i+1][1] );
42 printf("%d\n",sum);
43 }
44 return 0;
45 }

轉載于:https://www.cnblogs.com/ACShiryu/archive/2011/08/13/poj2479.html

總結

以上是生活随笔為你收集整理的poj2479与poj2593 ， 同一道DP题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。