OI

【动态规划】石子合并

【记忆化搜索】P1880
这题卡了好久……

首先是动规的问题，因为当前合并的石子分数只和两石子的个数有关，取决于之前的合并状态，而之前的合并最优时取得最优。

所以设F[i][j]表示区间[i,j]的最大得分

F[i][j]=max{F[i][k]+F[k+1][j]+sum(i,j)}(i<k<j)

因为是这样，所以递推起来应该是类似于线段树（？）之类，最下面的叶子节点是两两合并的值，每个父节点取子节点通过转移方程的最优值，根节点记录解。如此，就应该从1（2？）枚举区间长度，然后再递推，以防顺序混乱了。

（结果卡就卡递推上了……

因此就引入了记忆化搜索。还是原来的动规思想，然而却不需要设计递推次序，有结果就直接调用，没结果就递归求解，潇洒。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include<stdio.h>
#define inf 2147483647
int a[205]={0},pre[205]={0};
int f1[205][205]={0},f2[205][205]={0};
int sum(int st,int ed){
    return pre[ed]-pre[st-1];
}

int dfsmax(int l,int r){
    if(l==r)return 0;
    if(f1[l][r]!=0)return f1[l][r];
    int k,max=0,t;
    for(k=l;k<r;k++){
        t=dfsmax(l,k)+dfsmax(k+1,r)+sum(l,r);
        if(max<t)max=t;
    }
    f1[l][r]=max;
    return max;
}

int dfsmin(int l,int r){
    if(l==r)return 0;
    if(f2[l][r]!=0)return f2[l][r];
    int k,min=inf,t;
    for(k=l;k<r;k++){
        t=dfsmin(l,k)+dfsmin(k+1,r)+sum(l,r);
        if(min>t)min=t;
    }
    f2[l][r]=min;
    return min;
}

int main(){
    int n,i,max=0,min=inf;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[n+i]=a[i];
    }
    for(i=1;i<=2*n;i++)
      pre[i]=pre[i-1]+a[i];
    
    dfsmax(1,2*n);
    dfsmin(1,2*n);
    
    for(i=1;i<=n;i++){
        if(min>f2[i][n+i-1])min=f2[i][n+i-1];
        if(max<f1[i][n+i-1])max=f1[i][n+i-1];
    }
    printf("%d\n%d",min,max);
    return 0;
}