转载

poj 1651 区间dp

http://poj.org/problem?id=1651

题目意思是给你给你一串数字序列，没次你删除其中一个数a[i]，如何将得到a[i-1] * a[i] * a[i+1]点数，然后剩下的数重新拼成一个新的序列。问你最少能得到多少点数

对于一个区间(l, r),如果最后删除的是k位置的数的话，将得到a[l]*a[k]*a[r]分，而要得到这个情况的前提是吧区间(l, k) 和(k, r)的中间数字删掉所以的转移方程是

DP(l, r) = DP(l, k) + DP(k, r) + a[l]*a[k]*a[r];

#include <cstdio> #include <cstring> #include <iostream>  #include <algorithm> using namespace std; const int INF = 999999999; int a[102]; int dp[102][102]; int DP(int l, int r) {  if (dp[l][r] != -1) {   return dp[l][r];  }  if (r - l < 2 ) {   return dp[l][r] = 0;  }  int tmp = INF;  for (int k=l+1; k<=r-1; k++) {   int ans = DP(l, k) + DP(k, r) + a[l] * a[k] * a[r];   if (ans < tmp) {    tmp = ans;   }  }  return dp[l][r] = tmp; } int main () {  int n;  cin >> n;  for (int i=0; i<n; i++) {   cin >> a[i] ;  }  memset(dp, -1, sizeof(dp));  int ans = DP(0, n-1);  cout << ans << endl;  return 0; }