【记忆化搜索】P1063（尝到甜头又来一遍……）
尽管卡了好久，还是得承认和石子合并挺像的……
设F[i][j]表示区间[i,j]的最优值
F[i][j]=max{F[i][k]+F[k][j]+a[i]*a[k]*a[j]},i<k<j
这里遍历的i,j,k就是每次选择合并的珠子，由于只消耗中间一个珠子（即左右珠子仍需要再次合并），所以是F[i][k]+F[k][j]；累加的a[i]*a[k]*a[j]即每次的得分了。
于是故技重施记忆化搜索：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<stdio.h>
int a[205]={0},f[205][205]={0};
int dfs(int l,int r){
if(l==r)return 0;
if(f[l][r])return f[l][r];
int k,max=0,t;
for(k=l+1;k<r;k++){
t=dfs(l,k)+dfs(k,r)+a[l]*a[k]*a[r];
if(max<t)max=t;
}
f[l][r]=max;
return max;
}
int main(){
int n,i,max=0,t;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
a[n+i]=a[i];
}
for(i=1;i<=n;i++){
t=dfs(i,n+i);
if(max<t)max=t;
}
printf("%d",max);
return 0;
}
|
想明白就是想明白，没想明白就会一直卡，也许DP就是这样吧……