hihocoder 1636 2017 ICPC beijing J

发表于 | 分类于 | 浏览 次

题解

现在一次必须合并 k 堆k∈[L,R]，也就是说合并的堆数不小于L，不大于R。
每次合并的耗费。依然是石子总重。
那么显然合并前。我们需要知道。有多少堆合并了。
对于堆数不在[L,R]的，不能合并。
令：$dp[k][l][r]$表示
区间$[l,r]$合并成k段的耗费。
$w[l,r]$表示，区间$[l,r]$石子总重。
所以：
$$dp[k][l][r]=\min_{t=l+k-2}^{r-1}(dp[k-1][l][t]+dp[1][t+1][r])$$
特别的当：
$$dp[1][l][r]=\min_{k=L}^R(dp[k][l][r]+w[l , r])$$

代码

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
#include <cstdio>
#include "iostream"
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
typedef long long ll;
typedef unsigned long long ull;
const ll INF = 1e18;
const ll MAXN=110;
const ll MOD=1000000007;
ll dp[MAXN][MAXN][MAXN];
ll a[MAXN],s[MAXN];
int main(int argc, char const *argv[]) {
    ll n,L,R;
    while (cin>>n>>L>>R) {
        for(int i=1;i<=n;++i)
            scanf("%lld",&a[i]);
        s[0]=0;
        for(int i=1;i<=n;++i)
            s[i]=s[i-1]+a[i];
        Met(dp,0x3f);
        for(int k=1;k<=R;++k)
            for(int l=1;l<=n-k+1;++l)
                dp[k][l][l+k-1]=0;
        for(int len=L;len<=n;++len)
            for(int l=1;l<=n-len+1;++l)
                for(int k=2;k<=len && k<=R;++k)
                {
                    ll r=l+len-1;
                    for(int t=l+k-2;t<=r-1;++t)
                        dp[k][l][r]=min(dp[k][l][r],dp[k-1][l][t]+dp[1][t+1][r]);
                    if(k>=L && k<=R)
                    dp[1][l][r]=min(dp[1][l][r],dp[k][l][r]+s[r]-s[l-1]);
                }
        if(dp[1][1][n]>=dp[0][0][0])
            puts("0");
        else printf("%lld\n", dp[1][1][n]);
    }
    return 0;
}