比賽結果如何呢？充滿感慨~ 參加這個比賽，發現確實要成功accept有點難度，算是見識到了，還是ACM大佬厲害。
小白直接上題目了。
Drink
Problem Description
我們有 n 種不同的飲料，每種飲料有無限多瓶，第 i 種飲料一瓶提供 x[i] 毫升的水分，包含 y[i] 卡路里。

現在我們需要選擇一種飲料一直喝，直到補充了至少 mm 毫升的水分，我們想使得攝入的卡路里總和最小。請求出這個最小值。
一旦打開一瓶飲料，就一定要喝完。

Input
第一行一個整數 test(1≤test≤100) 表示數據組數。 對于每組數據，第一行兩個整數 n,m(1≤n≤100,1≤m≤10000)。 接下來 nn 行，每行兩個整數x[i],y[i] (1≤x[i],y[i]≤100)。

Output
對于每組數據，一行一個整數表示答案。

Sample Input 2 1 10 3 3 2 10 3 3 2 1 Sample Output 12 5

一看到題目，感覺跟0-1背包問題很類似，所以我嘗試了動態規劃的方法，結果本地測試沒問題，提交竟然wrong answer。調試好一會，用了直接的思路解決問題。
Accept代碼：

#include<bits/stdc++.h> using namespace std; int main() {int m; cin>>m;while(m--){int n, c, num=100000;cin>>n>>c;for(int i = 1; i <= n; i++){int x, y; cin>>x>>y;if(c%x==0)num = min(num,c/x*y);else num = min(num,(c/x+1)*y);}cout<<num<<"\n";}return 0; }

目前官方提示：對于每一種飲料，都可以算出最少需要多少瓶，從而知道最少攝入多少卡路里，從中找個最優值。
回頭看當時的做法，思路差不多一樣，直接明了。

GPA
Problem Description
小沃沃一共參加了 4 門考試，每門考試滿分 100 分，最低 0 分，分數是整數。

給定四門考試的總分，請問在最優情況下，四門課績點的和最高是多少？

分數與績點之間的對應關系如下：

95~100 4.3
90~94 4.0
85~89 3.7
80~84 3.3
75~79 3.0
70~74 2.7
67~69 2.3
65~66 2.0
62~64 1.7
60~61 1.0
0~59 0

Input
第一行一個正整數 test(1 \le test \le 401)test(1≤test≤401) 表示數據組數。 接下來 testtest行，每行一個正整數 xx 表示四門考試的總分 (0≤x≤400)。

Output
對于每組數據，一行一個數表示答案。答案保留一位小數。

Sample Input 2 0 400 Sample Output 0.0 17.2

Accept代碼：

#include<bits/stdc++.h> using namespace std; double maxnum; const int N=11; int low_g[N]={95,90,85,80,75,70,67,65,62,60,0};//每檔次績點對應最低分 double scores[N]={4.3,4.0,3.7,3.3,3.0,2.7,2.3,2.0,1.7,1.0,0};//績點 double score_to_grade(double score)//根據分數得出相應績點 {if(score>=95)return scores[0];else if(score>=90)return scores[1];else if(score>=85)return scores[2];else if(score>=80)return scores[3];else if(score>=75)return scores[4];else if(score>=70)return scores[5];else if(score>=67)return scores[6];else if(score>=65)return scores[7];else if(score>=62)return scores[8];else if(score>=60)return scores[9];elsereturn scores[10]; } void dfs(int i,int sum,double score)//深度搜索 {if(sum<0)return;if(i==3)//最多4門課{maxnum=max(maxnum,score_to_grade(sum)+score);//取最大績點和 return ;}for(int j=0;j<N;j++)//循環，枚舉每門課的分數檔次能夠獲得的績點 dfs(i+1,sum-low_g[j],score+scores[j]);//深度搜優先索 } int main() {int r,total;cin>>r;while(r--){cin>>total;maxnum=0;dfs(0,total,0);cout<<setiosflags(ios::fixed)<<setprecision(1);//保留一位小數 cout<<maxnum<<'\n';}return 0; }

目前官方提示：暴力做法：枚舉四門課的成績，按規則算算GPA。 優秀做法：對于每一檔績點，分數取最低一定是最優的，那么我們就可以用枚舉分數的檔次取代枚舉具體的分數。
這個思路覺得不是暴力做法，對給定的總成績，深度優先搜索，枚舉出每門課的分數檔次能夠獲得的績點，進行遞歸，最后取最大績點和。

Dec

Problem Description
初始有 a, b兩個正整數，每次可以從中選一個大于 1 的數減 1，最后兩個都會減到 1，我們想知道在過程中兩個數互質的次數最多是多少。
Input
第一行一個正整數test(1≤test≤1000000) 表示數據組數。
接下來 test 行，每行兩個正整數 a,b(1≤a,b≤1000)。
Output
對于每組數據，一行一個整數表示答案。

Sample Input 1 2 3 Sample Output 4樣例解釋 2 3 -> 1 3 -> 1 2 -> 1 1

Accept代碼：

#include<iostream> using namespace std;const int n_max=1005; int test; int a,b;int f[n_max+1][n_max+1]; int gcd(int a,int b)//輾轉相除求最小公約數 {int temp=a;while(a%b){a=b;b=temp%b;temp=a;}return b; } void dp() {for(int i=1;i<=n_max;i++)//動態規劃 {for(int j=1;j<=n_max;j++){int t=0;if (gcd(i,j)==1)//如果最大公約數是1則互質t=1;f[i][j]=max(f[i-1][j]+t,f[i][j-1]+t);//取最大值 }} } int main() {cin>>test;dp();for(int k=0; k<test; k++){scanf("%d%d",&a,&b); //輸入用cin/cout都會超時printf("%d\n",f[a][b]);}}

官方提示：用 f[i][j]f[i][j] 表示第一個數字從 ii 開始減，第二個數字從 jj 開始減的情況下最多有多少對互質的數字，f[i][j]f[i][j] 從 f[i-1][j]f[i?1][j] 或 f[i][j-1]f[i][j?1] 轉移過來。
很明顯，使用動態規劃的方法解決直觀明了，開始看題目以為是要數學推導，找規律。

總結

以上是生活随笔為你收集整理的2020年百度之星程序设计大赛-初赛一（Drink、GPA、Dec）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。