1 条题解
-
0
#include <iostream> #include <vector> #include <algorithm> using namespace std; int pizzaAmount; vector<int> pizzaPieces; //三维数组,result[left][right][0]表示吃货能吃到的最大数,result[left][right][1]表示馋嘴能吃到的最大数 vector<vector<vector<unsigned long>>> result; //披萨是一个圆,通过这个函数让数组首尾相接 int legalIndex(int input) { if (input < 0) return pizzaAmount - 1; else if (input >= pizzaAmount) return 0; return input; } //返回从left到right,某人能吃到的最大的披萨,turn=0表示吃货,turn=1表示馋嘴 unsigned long getMax(int left, int right, int turn) { if (left == right) { //最后一块饼,因为pizza数为奇数,吃货先吃,所以他必定比馋嘴多吃一个也就是最后这一个 if (turn == 0) return pizzaPieces[left]; else return 0; } //如果已有结果则直接返回 if (result[left][right][turn] > 0) return result[left][right][turn]; //吃货的回合,选择两种情况下(吃左边/吃右边)最大的 if (turn == 0) { unsigned long eatLeft = getMax(legalIndex(left - 1), legalIndex(right), 1) + pizzaPieces[left]; unsigned long eatRight = getMax(legalIndex(left), legalIndex(right + 1), 1) + pizzaPieces[right]; result[left][right][0] = max(eatLeft, eatRight); } //馋嘴的回合,在左和右两个选择中固定选最大的 else { if (pizzaPieces[left] > pizzaPieces[right]) result[left][right][1] = getMax(legalIndex(left - 1), right, 0); else result[left][right][1] = getMax(left, legalIndex(right + 1), 0); } return result[left][right][turn]; } int main(int argc, char *argv[]) { cin >> pizzaAmount; for (int i = 0; i < pizzaAmount; i++) { int temp; cin >> temp; pizzaPieces.push_back(temp); } //初始化三维数组 result = vector<vector<vector<unsigned long>>>(pizzaAmount, vector<vector<unsigned long>>(pizzaAmount, vector<unsigned long>(2, 0))); unsigned long max = 0; for (int i = 0; i < pizzaAmount; i++) { //一开始从吃货开始吃 unsigned long get = getMax(legalIndex(i - 1), legalIndex(i + 1),1)+pizzaPieces[i]; if (get > max) max = get; } cout << max << endl; return 0; }
- 1
信息
- ID
- 110
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 186
- 已通过
- 65
- 上传者