ccf試題壓縮代碼

2019-11-11 04:01:45

字體：大中小

來源：轉載

供稿：網友

題外話：這道題是典型的石子合并問題。所謂石子問題，就是有N堆石子，現要將石子有序的合并成一堆，規定如下：每次只能移動2堆石子合并，合并花費為新合成的一堆石子的數量。求將這N堆石子合并成一堆的總花費最小（或最大）。這類問題有三種情況：

每次移動任意兩堆石子（赫夫曼問題）

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

#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]; } 每次移動的相鄰兩堆石子（石子堆排列成直線）

設dp[i][j]表示第i到第j堆石子合并的最優值，sum[i][j]表示第i到第j堆石子的總數量。那么就有狀態轉移公式：這里寫圖片描述

#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;}

每次移動的相鄰兩堆石子（石子堆排列成環形）

這里寫圖片描述

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

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