NYOJ 737：http://acm.nyist.net/JudgeOnline/problem.php?pid=737 代码：
#include <cstdio> #include <iostream> #include <cstring> #define sf scanf #define pf printf using namespace std; typedef long long LL; const int maxn = 205; /* 题意： N堆石子排成一排 每次可以合并相邻的两堆石子 合并的代价是两堆石子的数量的和 在经过N - 1次合并和，N堆石子合并为一堆石子，问最小的代价是多少 DP[i][j] 表示将第i堆和第j堆合并为一堆的最小花费 那么DP[i][j] 就可以表示成 DP[i][j] = min{DP[i][k] + DP[k + 1][j] + COST((i ~ k):(k + 1 ~ j))} */ const LL INF = 0x3f3f3f3f; LL DP[maxn][maxn]; LL A[maxn]; LL DPS(int l,int r){ if(DP[l][r] != -1) return DP[l][r]; LL& ans = DP[l][r]; ans = INF; LL L = 0,R = 0; for(int i = l;i <= r;++i) R += A[i]; for(int k = l;k < r;++k){ L += A[k],R -= A[k]; ans = min(ans,L + R + DPS(l,k) + DPS(k + 1,r)); } return ans; } int main(){ int n; while( ~sf("%d",&n) ){ for(int i = 0;i < n;++i) sf("%lld",A + i); memset(DP,-1,sizeof(DP)); for(int i = 0;i < n;++i) DP[i][i] = 0; DPS(0,n - 1); pf("%lld\n",DP[0][n - 1]); } return 0; }POJ 2955：http://poj.org/problem?id=2955 代码：
#include <cstdio> #include <iostream> #include <cstring> #define sf scanf #define pf printf using namespace std; /* 题意：给一个只包含‘[’，‘]’，‘(’，‘)’的字符串求在这个字符串的一个最长的子串 是一个合法括号字符 DP[i][j] 表示将i 到 j 变为合法字符串要删除的最少字符数 那么 DP[i][j] = min{DP[i][k] + DP[k + 1][j]};check(s[i],s[j]) DP[i][j] = min(DP[i][j],DP[i + 1][j - 1]); */ const int INF = 0x3f3f3f3f; const int maxn = 105; int DP[maxn][maxn]; char s[maxn]; int DPS(int l,int r){ if(~DP[l][r]) return DP[l][r]; int& ans = DP[l][r]; ans = INF; if(s[l] == '(' && s[r] == ')' || s[l] == '[' && s[r] == ']') ans = min(ans,DPS(l + 1,r - 1)); for(int k = l;k < r;++k){ ans = min(ans,DPS(l,k) + DPS(k + 1,r)); } return ans; } int main(){ while(sf("%s",s)){ if(s[0] == 'e') break; int len = strlen(s); memset(DP,-1,sizeof(DP)); for(int i = 0;i < len;++i){ DP[i][i] = 1; DP[i + 1][i] = 0; } pf("%d\n",len - DPS(0,len - 1)); } return 0; }NYOJ 746：http://acm.nyist.net/JudgeOnline/problem.php?pid=746
#include <cstdio> #include <iostream> #include <queue> #include <cstring> #define sf scanf #define pf printf using namespace std; typedef long long int LL; /* 分类 区间DP入门题 题意： 要求将一个整数N 划分成M段 使这M段的乘积最大 现在我们将整数 看作一个由数字组成的字符串 那么 DP[l][r][m] 表示将子串(l - r)划分成M段的最大乘积的值 那么DP[l][r][m] max{DP[l][k][p] * DP[k + 1][r][q]} (k >= l ^ k < r ^ (p + q) == m) */ const int maxn = 20; LL DP[maxn][maxn][maxn]; LL G[maxn],F[maxn]; int len; char s[maxn]; LL DPS(int l,int r,int m){ if(~DP[l][r][m]) return DP[l][r][m]; LL& ans = DP[l][r][m] = 0; if(r - l + 1 < m) ans = 0; else if(m == 1){ ans = G[l] / F[r + 1]; } else for(int k = l;k < r;++k){ for(int p = 1;p <= m;++p){ for(int q = 1;q <= m;++q){ if(p + q == m){ ans = max(ans,DPS(l,k,p) * DPS(k + 1,r,q)); } } } } // pf("%d %d %d %lld\n",l,r,m,ans); return ans; } int main(){ int T;sf("%d",&T); while( T-- ){ memset(DP,-1,sizeof(DP)); int n,m; sf("%s %d",s,&m); len = n = strlen(s); F[len] = 1; G[len] = 0; for(int i = len - 1;~i;--i) { F[i] = F[i + 1] * 10; G[i] = G[i + 1] + (s[i] - '0') * F[i + 1]; } // pf("%lld\n",G[0] / F[1]); pf("%lld\n",DPS(0,n - 1,m)); } return 0; }