【文件输入】文件输入共两行。第一行为整数n (1<=n<=20)。第二行为a(1),a(2),...,a(n)这n个正整数，每个数字不超过100。 【文件输出】文件输出共3行。第一行为添加括号的方法。第二行为最终的中间和之和。第三行为n-1个中间和，按照从里到外，从左到右的顺序输出。 【样例输入】 【样例输出】 4 (4+((1+2)+3)) 4 1 2 3 19 3 6 10 【思路点拨】 f[i][j]：表示从i开始到第j个数合并为一个数所得到的最小和。 f[i][j]=min{f[i][k]+f[k+1][j]+sum[i][j]} sum[i][j]：表示从i到j之间的和。 #include
long a[21]={0},s[21]={0},f[21][21]={0},v[21][21]={0},s1=0; void out(long t,long w)
{ if(t==w){cout<
cout<<'+';out(v[t][w]+1,w);cout<<')'; }
long jia(long t,long w) { long x=0,y=0;
if(t==w)return a[t];
if(t==v[t][w]&&v[t][w]+1==w)
{cout<
if(t<=v[t][w])x=jia(t,v[t][w]);
if(v[t][w]+1<=w)y=jia(v[t][w]+1,w); cout< int main() { long n,i,j,k,t,min; cin>>n; for(i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];} for(i=n-1;i>0;i--) for(j=i+1;j<=n;j++) { min=99999999; for(k=i;k if(f[i][k]+f[k+1][j] out(1,n); cout< 【例题】：矩阵相乘1645 Description 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个m行、n列的矩阵（简称m×n的矩阵），B是一个n行、p列的矩阵（简称n×p的矩阵），则其乘积C=A×B是一个m×p的矩阵。其标准计算公式为： 由该公式知计算C=A×B总共需要进行m×n×p次的数乘法，我们将两个矩阵乘法次数定义为矩阵想乘的时间复杂度。 矩阵乘法满足矩阵乘法满足结合律（但不满足交换律），即对于D=A×B×C，可以有如下两种计算方式： 1、D=（A×B）×C 2、D=A×（B×C） 假设A是个10×100的矩阵、B是个100×5的矩阵，C是个5×50的矩阵，那么： ●按照第一种计算方法得到的时间复杂度是：10×100×5+10×5×50=7500； ●按照第一种计算方法得到的时间复杂度是：100×5×50+10×100×50=75000； 所以不同的计算顺序得到的时间复杂度是不一样的，现在的问题是：顺序给出n个矩阵的大小，请计算出它们的乘积的最小的时间复杂度。 Input 第一行输入一个正整数n，表示有n个矩阵。 接下来m行每行两个正整数Xi，Yi，其中第i行的两个数表示第i个矩阵的规模为Xi行、Yi列。所有的Xi、Yi<=100。 输入数据保证这些矩阵可以相乘。 Output:n个矩阵连乘最小时间复杂度。 Sample Input 3 10 100 100 5 5 50 Sample Output:7500 数据范围：n<=100。 【例题】能量项链1511 【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r,尾标记为n，则聚合后释放的能量为m*r*n(Mars单位)，新产生的珠子的头标记为m，尾标记为n。 需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。 例如：设N=4,4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为： (4⊕1)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。 【输入文件】输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 9 【输出文件】输出文件energy.out只有一行，是一个正整数E（E≤2.1*10），为一个最优聚合顺序所释放的总能量。 【输入样例】 4 2 3 5 10 【输出样例】710 【思路点拨】 环形问题解决思路： 1、 枚举断开点，使用n次DP找最优 2、 将长为n的环展开成(2*n-1)长的链，其中n后的部份复制1?n-1,子问题规模最大求到n,一次DP后输出n个规模为n 的子问题中最好的 设f[i][j]表示将从第i个珠子聚合到第j个珠子的最大释放能量。假设最后合并的位置为k和k+1，则： f[i][j]=max{f[i][k]+f[k+1][j]+a[i]*b[k]*b[j]},1<=i<=k<=j<=n 初始化：f[i][i]=0; ans=max{f[1][n],f[2][n+1]….+f[n][2n-1]} #include int a[205],b[205],f[205][205]; int main() { int ans=0,n,i,L,s,t; cin>>n; for(i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}// 环展开成链 for(i=1;i<=2*n-1;i++)b[i]=a[i+1]; b[2*n]=a[1]; for(L=2;L<=n;L++)//规模最大求到n for(s=1;s<=2*n-L+1;s++) { t=s+L-1; f[s][t]=0; for(i=s;i<=t-1;i++) f[s][t]=maxx(f[s][t],f[s][i]+f[i+1][t]+a[s]*b[i]*b[t]); } for(i=1;i<=n;i++)ans=maxx(ans,f[i][i+n-1]);// n个规模为n的子问题中最好的 cout< 【例题】多边形游戏2251 【问题描述】多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点组成的多边形。每个顶点赋予一个整数（不超过整型范围），每条边赋予一个运算符号“+”或“*”。所有的边按顺时针从0---n-1编号。在游戏的第一步，删除一条边，随后的n-1步按如下方式操作： （1）选择一条边E及由E相连的顶点V1，V2; （2）用一个新的顶点替代E及V1,V2，新顶点为v1与V2采用E的运算所得值。 当所有边被删除时游戏结束。游戏的得分就是最且那个顶点的值。 问题：对于给定的多边形，计算其最高得分。 【文件输入】第1行为一个整数N (1<=N<=50), 表示顶点数；第2行为一串字符表示顶点及边的序列如1+3*2*5+，该序列肯定正确,不必验证。 【文件输出】文件输出只有一行，表示最高得分。 【样例输入】 3 2+3*2+ 【样例输出】12 【数据范围】70%数据数据运算过程中不超过long范围 30%数据数据运算过程中超过long范围 【思路点拨】这是一道环形合并问题，主要思想同石子合并或能量项链，但要注意几点，由于顶点为整数，没有说明正整数，因此可能为负数，所以在处理过程中，要保留两个状态，即将从i点到j点合并成一点时的最大值和最小值，因为两个负数的最小乘起来可能最大。关于高精度问题，最好用封装的处理。 #include double f[101][101],g[101][101],max; int a[51],b[51],i,n,x; char c;bool tt; double work(double x,double y,int t) { if(t==0)return x+y; if(t==1)return x*y; } void dp() { int i,j,k;double temp; for(i=n-1;i>=1;i--) for(j=i+1;j<=n;j++) if(j-i<=(n+1)/2) { f[i][j]=-1e100; g[i][j]=1e100; for(k=i;k<=j-1;k++) { temp=work(f[i][k],f[k+1][j],b[k]); if(f[i][j] temp=work(f[i][k],g[k+1][j],b[k]); if(f[i][j] temp=work(g[i][k],f[k+1][j],b[k]); if(f[i][j] temp=work(g[i][k],g[k+1][j],b[k]); if(f[i][j] int main() { cin>>n;i=0; while(i { i++;x=0;tt=false; do{ cin>>c; if(c=='-'){tt=true;cin>>c;} if(c>='0'&&c<='9')x=x*10+(c-'0'); }while(c>='0'&&c<='9'); a[i]=x;if(tt)a[i]=-x; if(c=='+')b[i]=0;else b[i]=1; } for(i=1;i<=n;i++)f[i][i]=a[i]; for(i=n+1;i<=2*n-1;i++){f[i][i]=a[i-n];b[i]=b[i-n];} for(i=0;i<=100;i++) for(int j=0;j<=100;j++)g[i][j]=f[i][j]; n=2*n-1;double max=-1e100; dp(); n=(n+1)/2; for(i=1;i<=n;i++)if(max 【例题】凸多边形的划分1981 【问题描述】给定一个具有N(N<50)个顶点(从1到N编号)的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？ 【输入文件】第一行为顶点数N;第二行为N个顶点(从1到N)的权值。 【输出格式】最小的和的值。 【输入示例】 5 122 123 245 231 【输出示例】12214884 【思路点拨】首先，这是一个剖分问题，那么是否可以用我们上述所说的合并类动态规划解决呢？ 我们知道，对于任意一个凸多边形，如果我们从中去掉任意一个三角形后，可以变成三块，其中两块仍然为凸多边形，另一个为三角形。 设f[i][j](i 但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算。 #include typedef long long array[60]; array F[110][110],a,s1,s2,s3; long long n; void mark(array &c) { for(int i=1;i<=c[0];i++) {c[i+1]+=c[i]/100000;c[i]%=100000;} while (c[c[0]+1]) { c[0]++;c[c[0]+1]+=c[c[0]]/100000;c[c[0]]%=100000;} } void mul(long long a1,long long a2,long long a3,array &c) { memset(c,0,sizeof(c));c[0]=c[1]=1; for(int i=1;i<=c[0];i++)c[i]*=a1; mark(c); for(int i=1;i<=c[0];i++)c[i]*=a2; mark(c); for(int i=1;i<=c[0];i++)c[i]*=a3; mark(c); } void add(array a,array b,array &c) { memset(c,0,sizeof(c)); if(a[0]>b[0])c[0]=a[0];else c[0]=b[0]; for(int i=1;i<=c[0];i++)c[i]=a[i]+b[i]; mark(c); } bool check(array a,array b) { if(a[0] if(a[i] int main() { scanf(\ for(int i=1;i<=n;i++)scanf(\ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)F[i][j][0]=1; for(int i=n-2;i>=1;i--) for(int j=i+2;j<=n;j++) { F[i][j][0]=60; for(int k=i+1;k<=j-1;k++) { mul(a[i],a[k],a[j],s1); add(F[i][k],F[k][j],s2); add(s1,s2,s3); if(check(F[i][j],s3))memcpy(F[i][j],s3,sizeof(F[i][j])); } } printf(\ for(int i=F[1][n][0]-1;i>=1;i--)printf(\ printf(\} 思考： 最少正方形bsoi2973 LCS类型DP 【培训练习题】最长公共子序列1598 Description 一个给定的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X = < X1，X2，…，Xm >，则另一序列Z = < Z1，Z2，…，Zk > 是x的子序列是指存在一个严格递增的下标序列< i1，i2，…，ik >，使得对于所有 j=1，2，…，k 有： 例如，序列Z=< B，C，D，B >是序列X=< A，B，C，B，D，A，B >的子序列，相应的递增下标序列为< 2，3，5，7 >。给定两个子序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 在例如，若X=< A，B，C，B，D，A，B >和Y=< B，D，C，A，B，A >，则序列< B，C，A >是X和Y的一个公共子序列，序列< B，C，B，A >也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有一个长度大于4的公共子序列。 给定两个序列X = < X1，X2，…，Xm >和 Y = < Y1，Y2，…，Ym >，要找出X和Y的一个最长公共子序列。 Input 共有两行，每一行为一个大写字母构成的长度不超过2000的字符串，表示序列X和Y。 Output 一个非负正整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则文件仅有一行输出一个整数0。 Sample Input ABCBDAB BDCABA Sample Output 4 【算法分析】 1、阶段和状态： 设二维数组F，其下标和值的含义为： F[i][j]=x 表示字符串S1的前i个字符与字符串S2的前j个字符的最长公共子串长度为x。 2、状态转移方程： 由上面的叙述可知： F[i?1，j?1]?1? F[i,j]?max??Max{F[i?1，j]，F[i,j?1]}如果s[i]?p[j](如果s[i]??p[j]) 3、核心子程序： int main() { memset(f,0,sizeof(f)); cin>>s1>>s2; l1=s1.length();l2=s2.length(); s1=' '+s1;s2=' '+s2; for(i=1;i<=l1;i++) for(j=1;j<=l2;j++) if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); cout<