CCF(圧縮符号化):動的計画＋平行四角形最適化

あっしゅくコーディング

201612-4

最初はこの問題を見てハフマン符号化の問題だと思っていたが、結局ハフマン問題の変形だった.

ハフマン符号化は、任意の2つの石を合併するたびに行われ、ここでのテーマは隣接する2つの石を合併することであり、ここでの合併費用は、2つの石を合併し、すべての葉の結点を加えることである.

参考図解:https://blog.csdn.net/more_ugly_less_bug/article/details/60142954

石の問題:https://blog.csdn.net/acdreamers/article/details/18039073

#include 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
const int maxn=1003;
int n;
int sum[maxn];
int dp[maxn][maxn];
const int INF=0X3F3F3F3F;
//dp[i][j]=min(dp[i][k]+dp[k][j]+sum[j]-sum[i-1])
int main() {
    //freopen("in1.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int x;
    sum[0]=0;
    for(int i=1;i<=n;i++){
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    memset(dp,INF,sizeof(dp));
    for(int i=1;i<=n;i++){
        dp[i][i]=0;
    }
    for(int i=n;i>=1;i--){
        for(int j=i+1;j<=n;j++){
            for(int k=i;k

転載先:https://www.cnblogs.com/GarrettWale/p/11521214.html