poj1651 Multiplication Puzzle (区间dp)

题意：给n张牌，让你取出不包括两端的n-2张，每次取出时会获得相当于该牌和相邻两牌点数成绩的分数，要求最终分数最小

设f[i][j]为抽光区间[i,j]所获得的最小分数，然后

f[i][j]=min{f[i][k-1]+f[k+1][j]+val[i-1]*val[k]*val[j+1]}，i<=k<=j,i<j

f[i][j]=val[i-1]*val[i]*val[i+1] ,i==j

f[i][j]=0 ,i>j

然后就可以用$ $O (n^{3})$

$O (n^{3})$

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<queue>
 6 #include<cmath>
 7 #define inf 0x3f3f3f3f
 8 #define LL long long int
 9 using namespace std;
10 const int maxn=110;
11 
12 LL rd(){
13     LL x=0;char c=getchar();int neg=1;
14     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
15     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
16     return x*neg;
17 }
18 
19 int N;
20 int f[maxn][maxn][2],num[maxn];
21 
22 int main(){
23     int i,j,k,ans=inf;
24     N=rd();
25     for(i=1;i<=N;i++) num[i]=rd();
26     if(N==3){
27         printf("%d
",num[1]*num[2]*num[3]);return 0;
28     }
29     for(i=2;i<N;i++) f[1][i][0]=num[i-1]*num[i]*num[i+1];
30     for(i=2;i<=N-2;i++){
31         for(j=2;j<=N-i;j++){
32             f[i][j][0]=inf;
33             for(k=j;k<=j+i-1;k++){
34                 int a=f[k-j][j][0]+f[i-1-k+j][k+1][0]+num[j-1]*num[k]*num[i+j];
35                 if(a<f[i][j][0]){
36                     f[i][j][0]=a;f[i][j][1]=k;
37                 }
38             }
39             if(i==N-2) ans=min(ans,f[i][j][0]);
40         }
41     }printf("%d
",ans);
42     return 0;
43 }