Tyvj P3276

题目链接：http://www.tyvj.cn/p/3276

这题是一个动归题，一直没有想出动归的做法，后来求教别人之后写了一个记忆化搜索，只有出题者又给我提供了DP的解法，下面我来写写DP的写法

设置数组dp[i][j]，表示从位置j开始，后面i个数的最大值

去掉最右端的数：dp[i][j]=sum[i+j-2]-sum[j-1]-dp[i-1][j]+a[i+j-1]

去掉最左端的数：dp[i][j]=sum[i+j-1]-sum[j]-dp[i-1][j+1]+a[j]

（具体参看笔记）

然后再取左边和右边的最大值即可，很好的题目，确实值得一做

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<algorithm>
 8 #include<map>
 9 using namespace std;
10 const int maxn=1000+10;
11 int a[maxn],sum[maxn];
12 int dp[maxn][maxn];
13 int main()
14 {
15     int n;
16     while(cin>>n)
17     {
18         memset(dp,0,sizeof(dp));
19         memset(sum,0,sizeof(sum));
20         for(int i=1;i<=n;i++)
21         {
22             cin>>a[i];
23             sum[i]=sum[i-1]+a[i];
24         }
25         for(int i=1;i<=n;i++)
26             dp[1][i]=a[i];
27         for(int i=2;i<=n;i++)
28             for(int j=1;j<=n-i+1;j++)
29         {
30             dp[i][j]=sum[i+j-2]-sum[j-1]-dp[i-1][j]+a[i+j-1];  //去掉最右端的数
31             if(dp[i][j]<sum[i+j-1]-sum[j]-dp[i-1][j+1]+a[j])
32                 dp[i][j]=sum[i+j-1]-sum[j]-dp[i-1][j+1]+a[j];  //去掉最左端的数
33         }
34         cout<<dp[n][1]<<" "<<sum[n]-dp[n][1]<<endl;
35     }
36     return 0;
37 }

View Code

同时，我也把别人写的记忆化搜索的代码贴上去

Query(l, r)，表示当前先手在l-r能取到的最大分数，这个分数可能是取左边的得来的，也可能是取右边的得来的，

所以是它们的max，如果取的是左边，那么最后的分数是左边的分数，加上（剩下的和减去对方能取到的最大结果）

 1 #include <stack>
 2 #include <cstdio>
 3 #include <list>
 4 #include <cassert>
 5 #include <set>
 6 #include <iostream>
 7 #include <string>
 8 #include <vector>
 9 #include <queue>
10 #include <functional>
11 #include <cstring>
12 #include <algorithm>
13 #include <cctype>
14 #include <string>
15 #include <map>
16 #include <cmath>
17 #include <ext/pb_ds/assoc_container.hpp>
18 #include <ext/pb_ds/hash_policy.hpp>
19 using namespace std;
20 #define LL long long
21 #define ULL unsigned long long
22 #define SZ(x) (int)x.size()
23 #define Lowbit(x) ((x) & (-x))
24 #define MP(a, b) make_pair(a, b)
25 #define MS(arr, num) memset(arr, num, sizeof(arr))
26 #define PB push_back
27 #define X first
28 #define Y second
29 #define ROP freopen("input.txt", "r", stdin);
30 #define MID(a, b) (a + ((b - a) >> 1))
31 #define LC rt << 1, l, mid
32 #define RC rt << 1|1, mid + 1, r
33 #define LRT rt << 1
34 #define RRT rt << 1|1
35 const double PI = acos(-1.0);
36 const int INF = 0x3f3f3f3f;
37 const double eps = 1e-8;
38 const int MAXN = 5e4+10;
39 const int MOD = 9901;
40 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
41 int cases = 0;
42 typedef pair<int, int> pii;
43  
44 int arr[300], sum[300];
45 map<pii, int> mp;
46  
47 int Query(int l, int r)
48 {
49     if (mp.count(MP(l, r))) return mp[MP(l, r)];
50     if (l == r) return arr[l];
51     int ans;
52     ans = max(arr[l] + sum[r]-sum[l]-Query(l+1, r), arr[r] + sum[r-1]-sum[l-1]-Query(l, r-1));
53     mp[MP(l, r)] = ans;
54     return ans;
55 }
56  
57 int main()
58 {
59     //ROP;
60     int n;
61     scanf("%d", &n);
62     for (int i = 1; i <= n; i++)
63     {
64         scanf("%d", &arr[i]);
65         sum[i] = arr[i];
66         sum[i] += sum[i-1];
67     }
68     int ans = Query(1, n);
69     printf("%d %d
", ans, sum[n]-ans);
70     return 0;
71 }
72 
73  
74 Download as text

View Code

感悟就是我太弱了，已经不能忍，接下来无论是考研，还是创新项目，抑或是刷题，都必须好好努力了