首页 > 代码库 > 1176. Two Ends
1176. Two Ends
题目链接地址：http://soj.me/1176
题目大意：两头取数。第一个人随机取，第二个人用贪婪算法（每次都取大的），求两人取数在第一个人赢的情况下的最大分差。使用贪婪算法时，如果左右两边相等，取左边的。
核心算法：动态规划。
设数组arr[a][b]是在数列区间[a,b]上的最大分差。
递推公式：
1.第一个人取左边的数arr[a]
if(arr[a+1] >= arr[b]) point1 = input[a] - input[a+1] + dp(a+2,b);
else point1 = input[a] - input[b] + dp(a+1, b-1);
2.第一个人取右边的数arr[b]
if (input[a] >= input[b-1]) point2 = input[b] - input[a] + dp(a+1,b-1);
else point2 = input[b] - input[b-1] + dp(a,b-2);
arr[a][b] = point1 > point2 ? point1 : point2;
代码：
1 // 动态规划！ 2 #include <stdio.h> 3 4 #define N 1005 5 #define ENDLESS 100000 6 7 int arr[N][N]; 8 int input[N]; 9 10 int dp(int a, int b) {11 if (arr[a][b] != ENDLESS)12 return arr[a][b];13 14 if (a > b)15 return 0;16 17 // 第一个人取左边的数，第二个人贪婪算法18 int point1;19 if (input[a+1] >= input[b]) {20 point1 = input[a] - input[a+1] + dp(a+2,b);21 } else {22 point1 = input[a] - input[b] + dp(a+1, b-1);23 }24 25 // 第一个人取右边的数，第二个人贪婪算法26 int point2;27 if (input[a] >= input[b-1]) {28 point2 = input[b] - input[a] + dp(a+1,b-1);29 } else {30 point2 = input[b] - input[b-1] + dp(a,b-2);31 }32 33 arr[a][b] = point1 > point2 ? point1 : point2;34 35 return arr[a][b];36 }37 38 int main() {39 int n;40 int count = 0;41 while (scanf("%d", &n) != EOF) {42 if (n == 0)43 break;44 45 for (int i = 0; i < n; i++)46 scanf("%d", &input[i]);47 48 for (int i = 0; i < n; i++)49 for (int j = 0; j < n; j++)50 arr[i][j] = ENDLESS;51 52 printf("In game %d, the greedy strategy might lose by as many as %d points.\n", ++count, dp(0,n-1));53 }54 return 0;55 }
1176. Two Ends
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。