【CCF】路径压缩区间dp

【题意】

改编哈夫曼树，限制从左到右字母的编码按字典序递增

【思路】

因为是二进制编码，所以是二叉树；
因为是前缀码，所以每个字母都是叶子结点，不可能是内结点；
因为要按字典序递增，所以只能是相邻的结点结合，且排在前面的在左边，排在后面的在右边；
具有最优子结构性质：考虑f[i,j]，可以由f[i,k]和f[k,j]转换而来，只要找一个根结点，然后左右孩子分别为f[i,k]和f[k,j]的根结点，即dp[i][j]=dp[i,k]+dp[k,j]+c

【AC】

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<queue>
 8 
 9 using namespace std;
10 const int maxn=1e3+2;
11 const int inf=0x3f3f3f3f;
12 int a[maxn];
13 int dp[maxn][maxn];
14 int sum[maxn];
15 int n;
16 int main(){
17     while(~scanf("%d",&n)){
18         sum[0]=0;
19         for(int i=1;i<=n;i++){
20             scanf("%d",&a[i]);
21             sum[i]=sum[i-1]+a[i];
22         }
23         memset(dp,inf,sizeof(dp));
24         for(int i=1;i<=n;i++) dp[i][i]=0;
25         for(int l=2;l<=n;l++){
26             for(int i=1;i+l-1<=n;i++){
27                 int j=i+l-1;
28                 for(int k=i;k<j;k++){
29                     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
30                 }
31             } 
32         }
33         int ans=dp[1][n];
34         printf("%d
",ans);
35         
36     }
37     return 0;
38 }

【CCF】路径压缩 区间dp

相关推荐

【CCF】路径压缩区间dp