题目链接：https://atcoder.jp/contests/agc062/tasks/agc062_b
做法
非常有意思的一道题目。
我们考虑一个序列被切割以后进入一种如放的状态，简单来说就是我手里现在有两个序列可以拼起来。
当操作一次后会发现手里的两个序列变成了四个序列，而代价实际上就是原来两个序列裂成两个序列的代价之和（因为代价的计算公式是一次式）。
因此，显然，我们要把原串切成一堆上升序列，而代价都是可以自己独立统计后再加起来的，直接上区间 DP ，时间复杂度：$O(Kn^3)$ 。
无解的充分必要条件：最少的上升序列个数 $>2^K$ 。
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
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110
using namespace std;
typedef long long LL;
LL dp[N][N][N],C[N];
int n,K,a[N];
int main(){
scanf("%d%d",&n,&K);
for(int i=1;i<=K;i++)scanf("%lld",&C[i]);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
a[x]=i;
}
memset(dp,20,sizeof(dp));
int cnt=0;
for(int i=1;i<n;i++){
if(a[i]>a[i+1])cnt++;
}
for(int i=1;i<=K;i++)cnt>>=1;
if(cnt){printf("-1\n");return 0;}
for(int i=1;i<=n;i++){
dp[K+1][i][i]=0;
for(int j=i+1;j<=n;j++){
if(a[j]<a[j-1])break;
dp[K+1][i][j]=0;
}
}
for(int t=K;t>=1;t--){
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
dp[t][i][j]=dp[t+1][i][j];
for(int k=i;k<j;k++)dp[t][i][j]=min(dp[t+1][i][k]+dp[t+1][k+1][j]+(j-k)*C[t],dp[t][i][j]);
}
}
}
printf("%lld\n",dp[1][1][n]);
return 0;
}
|
