首页 > 代码库 > sicily 1176 two ends
sicily 1176 two ends
动态规划问题,每一步都分两种情况,然后选出最合适的那种
#include "iostream" #include "memory.h" #include "stdio.h" using namespace std; const int MAX = 1005; int dp[MAX][MAX]; int largest; int arr[MAX]; int call(int start, int end){ if (start >= end) return 0; if (dp[start][end] != -1) //看先前有没算过这一步,如果有就直接返回 return dp[start][end]; else { int left_sum = 0, right_sum = 0; //player1 选择左边 if (arr[start + 1] >= arr[end]){ //player2 选择左边 left_sum = arr[start] - arr[start + 1] + call(start + 2, end); } else { left_sum = arr[start] - arr[end] + call(start + 1, end - 1); } //player1 选择右边 if (arr[start] >= arr[end - 1]){ //player2 选择右边 right_sum = arr[end] - arr[start] + call(start + 1, end - 1); } else { right_sum = arr[end] - arr[end - 1] + call(start, end - 2); } dp[start][end] = left_sum > right_sum ? left_sum : right_sum; //现在算dp return dp[start][end]; } } int main(){ int n; int gameId = 1; while (cin >> n && n){ memset(dp, -1, sizeof(dp)); memset(arr, 0, sizeof(arr)); largest = 0; for (int i = 1; i <= n; i++){ cin >> arr[i]; } int sum = call(1, n); printf("In game %d, the greedy strategy might lose by as many as %d points.\n", gameId ++, sum); } return 0; }
sicily 1176 two ends
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。