首页 > 代码库 > lightoj1031_区间dp
lightoj1031_区间dp
题目链接：http://lightoj.com/volume_showproblem.php?problem=1031
题目描述：
给出一个数列，两人轮流取数， 取完结束。每次可以取好多个数，但是只能从首或者尾为起点取连续的若干个。问最后两者取数和的绝对值最大为多少？
区间dp；
这道题我是在看了几份阶梯报告之后才想通的，现在想想很符合动态规划的要求
d(i, j)表示取数的人在数组i 到 j中能取的的最大值，然后中间枚举分割点，
ans = max(ans, sum[k]-sum[i-1]-d(k+1, j));
ans = max(ans, sum[j]-sum[k-1]-d(i, k-1));
采用和记忆化搜索的方式
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <set>11 #include <map>12 using namespace std;13 #define INF 0x3f3f3f3f14 typedef long long LL;15 16 int a[110], sum[110], dp[110][110];17 int solve(int l, int r)18 {19 if(dp[l][r] != -1 * INF)20 return dp[l][r];21 int res = sum[r]-sum[l-1];22 for(int i = l; i <= r; i++)23 {24 res = max(res, sum[i]-sum[l-1]-solve(i+1, r));25 res = max(res, sum[r]-sum[i-1]-solve(l, i-1));26 }27 dp[l][r] = res;28 return res;29 }30 int main()31 {32 int t, n;33 scanf("%d", &t);34 for(int ca = 1; ca <= t; ca++)35 {36 scanf("%d", &n);37 sum[0] = 0;38 for(int i = 1; i <= n; i++)39 for(int j = i; j <= n; j++)40 dp[i][j] = -1*INF;41 for(int i = 1; i <= n; i++)42 {43 scanf("%d", &a[i]);44 dp[i][i] = a[i];45 sum[i] = sum[i-1] + a[i];46 }47 printf("Case %d: %d\n", ca, solve(1, n));48 }49 return 0;50 }
lightoj1031_区间dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。