SRM533 D1 L1

Problem Statement

题目大意是给定N个有序数字，delete一个数字a[x]，产生能量a[x - 1] * a[x + 1]，问说产生的最大能量是多少，第一个和最后一个不能delete。

反过来考虑，insert操作，动态规划。

#include <iostream>#include <vector>using namespace std;int dp[55][55];class CasketOfStar{public:int go(vector<int> w, int L, int R) {if(dp[L][R]) return dp[L][R];for(int i = L + 1; i < R; i++) {int t = go(w, L, i) + go(w, i, R) + w[L] * w[R];if(t > dp[L][R]) dp[L][R] = t; }return dp[L][R]; }int maxEnergy(vector <int> w) { memset(dp, 0, sizeof(dp));return go(w, 0, w.size() - 1); }};

转载于:https://www.cnblogs.com/litstrong/archive/2012/02/24/2366791.html

相关资源：数据结构—成绩单生成器