思路

dfs+去重

關(guān)鍵

滿分的關(guān)鍵在于不同的前綴可能會遇到相同的情況，要直接排除這些情況，避免重復(fù)計算（單純dfs只有80分）

實現(xiàn)

這里采用數(shù)組f來記錄各種情況，通過traceback函數(shù)回溯

1 #include<iostream>2 #include<cstring>3 4 using namespace std;5 6 int a[305];7 int b[305];8 bool f[305][305][305];//去重
9 //int s=0; 10 int n; 11 void traceback(int i,int b1,int b2){ 12 /*if(s==1){ 13 return; 14 }*/ 15 if(f[i][b1][b2])return; 16 f[i][b1][b2]=true; 17 if(i>=n){ 18 if((b1+b2)/2==a[n-1]){ 19 for(int j=0;j<n;j++){ 20 cout<<b[j]<<' '; 21 } 22 exit(0); 23 } 24 25 } 26 else{ 27 for(int j=0;j<3;j++){//考慮除法取整的情況 28 b[i]=a[i-1]*3+j-b2-b1; 29 if(b[i]<=0){ 30 continue; 31 } 32 traceback(i+1,b[i],b[i-1]); 33 /*if(s==1){ 34 return; 35 }*/ 36 } 37 } 38 return; 39 } 40 41 int main(){ 42 memset(f,false,sizeof(f)); 43 cin>>n; 44 for(int i=0;i<n;i++){ 45 cin>>a[i]; 46 } 47 48 int lim=2*a[0]; 49 for(int i=1;i<=lim;i++){ 50 b[0]=i; 51 for(int j=0;j<2;j++){//考慮除法取整的情況 52 b[1]=lim+j-b[0]; 53 if(b[1]<=0){ 54 continue; 55 } 56 traceback(2,b[1],b[0]); 57 /*if(s==1){ 58 return 0; 59 }*/ 60 } 61 } 62 63 return 0; 64 }

題目

問題描述 在一條街上有n個賣菜的商店，按1至n的順序排成一排，這些商店都賣一種蔬菜。
　　第一天，每個商店都自己定了一個正整數(shù)的價格。店主們希望自己的菜價和其他商店的一致，第二天，每一家商店都會根據(jù)他自己和相鄰商店的價格調(diào)整自己的價格。具體的，每家商店都會將第二天的菜價設(shè)置為自己和相鄰商店第一天菜價的平均值（用去尾法取整）。
　　注意，編號為1的商店只有一個相鄰的商店2，編號為n的商店只有一個相鄰的商店n-1，其他編號為i的商店有兩個相鄰的商店i-1和i+1。
　　給定第二天各個商店的菜價，可能存在不同的符合要求的第一天的菜價，請找到符合要求的第一天菜價中字典序最小的一種。
　　字典序大小的定義：對于兩個不同的價格序列(a₁, a₂, ..., a_n)和(b₁, b₂, b₃, ..., b_n)，若存在i (i>=1), 使得a_i<b_i，且對于所有j<i，a_j=b_j，則認為第一個序列的字典序小于第二個序列。 輸入格式 輸入的第一行包含一個整數(shù)n，表示商店的數(shù)量。
　　第二行包含n個正整數(shù)，依次表示每個商店第二天的菜價。 輸出格式 輸出一行，包含n個正整數(shù)，依次表示每個商店第一天的菜價。 樣例輸入 8
2 2 1 3 4 9 10 13 樣例輸出 2 2 2 1 6 5 16 10 數(shù)據(jù)規(guī)模和約定 對于30%的評測用例，2<=n<=5，第二天每個商店的菜價為不超過10的正整數(shù)；
　　對于60%的評測用例，2<=n<=20，第二天每個商店的菜價為不超過100的正整數(shù)；
　　對于所有評測用例，2<=n<=300，第二天每個商店的菜價為不超過100的正整數(shù)。
　　請注意，以上都是給的第二天菜價的范圍，第一天菜價可能會超過此范圍。

?

轉(zhuǎn)載于:https://www.cnblogs.com/Gru-blog/p/11260539.html

總結(jié)

以上是生活随笔為你收集整理的180904 再卖菜 ccf的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。