ccf試題壓縮代碼

2019-11-11 04:00:23

字體：大中小

供稿：網(wǎng)友

題外話：這道題是典型的石子合并問題。所謂石子問題，就是有N堆石子，現(xiàn)要將石子有序的合并成一堆，規(guī)定如下：每次只能移動(dòng)2堆石子合并，合并花費(fèi)為新合成的一堆石子的數(shù)量。求將這N堆石子合并成一堆的總花費(fèi)最小（或最大）。這類問題有三種情況：

每次移動(dòng)任意兩堆石子（赫夫曼問題）

每次取最小的兩堆石子相加，直到合并為一堆

#include <iostream>#include<stdio.h>#include<queue>#include<algorithm>using namespace std;int a[102];int main(){ int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); } int sum=0; for(int i=0;i<n-1;i++) { sort(a,a+n);//每一次都要重新排序 a[i+1]+=a[i]; sum+=a[i+1]; } 每次移動(dòng)的相鄰兩堆石子（石子堆排列成直線）

設(shè)dp[i][j]表示第i到第j堆石子合并的最優(yōu)值，sum[i][j]表示第i到第j堆石子的總數(shù)量。那么就有狀態(tài)轉(zhuǎn)移公式：這里寫圖片描述

#include <iostream>using namespace std;int sum[1010];int num[1010];int dp[1010][1010];const int INF=1 << 30;int getMin(int a[],int n){ for(int i=0;i<n;i++) { dp[i][i]=0; } for(int v=1;v<n;v++) { for(int i=0;i<n-v;i++) { int j=i+v; dp[i][j]=INF; int tmp=sum[j]-(i > 0 ? sum[i-1]:0); for(int k=i;k<j;k++) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+tmp); } } } return dp[0][n-1];}int main(){ int n; cin>>n; for(int i=0;i<n;i++) { cin>>num[i]; } sum[0]=num[0]; for(int i=1;i<n;i++) { sum[i]=sum[i-1]+num[i]; } cout<<getMin(num,n)<<endl; return 0;}

每次移動(dòng)的相鄰兩堆石子（石子堆排列成環(huán)形）

這里寫圖片描述

#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int INF = 1 << 30; const int N = 205; int mins[N][N]; int maxs[N][N]; int sum[N],a[N]; int minval,maxval; int n; int getsum(int i,int j) { if(i+j >= n) return getsum(i,n-i-1) + getsum(0,(i+j)%n); else return sum[i+j] - (i>0 ? sum[i-1]:0); } void Work(int a[],int n) { for(int i=0;i<n;i++) mins[i][0] = maxs[i][0] = 0; for(int j=1;j<n;j++) { for(int i=0;i<n;i++) { mins[i][j] = INF; maxs[i][j] = 0; for(int k=0;k<j;k++) { mins[i][j] = min(mins[i][j],mins[i][k] + mins[(i+k+1)%n][j-k-1] + getsum(i,j)); maxs[i][j] = max(maxs[i][j],maxs[i][k] + maxs[(i+k+1)%n][j-k-1] + getsum(i,j)); } } } minval = mins[0][n-1]; maxval = maxs[0][n-1]; for(int i=0;i<n;i++) { minval = min(minval,mins[i][n-1]); maxval = max(maxval,maxs[i][n-1]); } } int main() { while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) scanf("%d",&a[i]); sum[0] = a[0]; for(int i=1;i<n;i++) sum[i] = sum[i-1] + a[i]; Work(a,n); printf("%d %d/n",minval,maxval); } return 0; }

好，下面看這道題：

問題描述　　給定一段文字，已知單詞a1, a2, …, an出現(xiàn)的頻率分別t1, t2, …, tn。可以用01串給這些單詞編碼，即將每個(gè)單詞與一個(gè)01串對應(yīng)，使得任何一個(gè)單詞的編碼（對應(yīng)的01串）不是另一個(gè)單詞編碼的前綴，這種編碼稱為前綴碼。　　使用前綴碼編碼一段文字是指將這段文字中的每個(gè)單詞依次對應(yīng)到其編碼。一段文字經(jīng)過前綴編碼后的長度為：　　L=a1的編碼長度×t1+a2的編碼長度×t2+…+ an的編碼長度×tn。　　定義一個(gè)前綴編碼為字典序編碼，指對于1 ≤ i < n，ai的編碼（對應(yīng)的01串）的字典序在ai+1編碼之前，即a1, a2, …, an的編碼是按字典序升序排列的。　　例如，文字E A E C D E B C C E C B D B E中， 5個(gè)單詞A、B、C、D、E出現(xiàn)的頻率分別為1, 3, 4, 2, 5，則一種可行的編碼方案是A:000, B:001, C:01, D:10, E:11，對應(yīng)的編碼后的01串為1100011011011001010111010011000111，對應(yīng)的長度L為3×1+3×3+2×4+2×2+2×5=34。　　在這個(gè)例子中，如果使用哈夫曼(Huffman)編碼，對應(yīng)的編碼方案是A:000, B:01, C:10, D:001, E:11，雖然最終文字編碼后的總長度只有33，但是這個(gè)編碼不滿足字典序編碼的性質(zhì)，比如C的編碼的字典序不在D的編碼之前。　　在這個(gè)例子中，有些人可能會想的另一個(gè)字典序編碼是A:000, B:001, C:010, D:011, E:1，編碼后的文字長度為35。　　請找出一個(gè)字典序編碼，使得文字經(jīng)過編碼后的長度L最小。在輸出時(shí)，你只需要輸出最小的長度L，而不需要輸出具體的方案。在上面的例子中，最小的長度L為34。輸入格式　　輸入的第一行包含一個(gè)整數(shù)n，表示單詞的數(shù)量。　　第二行包含n個(gè)整數(shù)，用空格分隔，分別表示a1, a2, …, an出現(xiàn)的頻率，即t1, t2, …, tn。請注意a1, a2, …, an具體是什么單詞并不影響本題的解，所以沒有輸入a1, a2, …, an。輸出格式　　輸出一個(gè)整數(shù)，表示文字經(jīng)過編碼后的長度L的最小值。樣例輸入 5 1 3 4 2 5 樣例輸出 34 樣例說明　　這個(gè)樣例就是問題描述中的例子。如果你得到了35，說明你算得有問題，請自行檢查自己的算法而不要懷疑是樣例輸出寫錯(cuò)了。評測用例規(guī)模與約定　　對于30%的評測用例，1 ≤ n ≤ 10，1 ≤ ti ≤ 20；　　對于60%的評測用例，1 ≤ n ≤ 100，1 ≤ ti ≤100；　

屬于石子合并的第二種情況。對應(yīng)的100分代碼：