北华大学第五届程序设计竞赛春季联赛C-D-E题hrd535523596的博客-

北华大学第五届程序设计竞赛春季联赛

C.种花
题意：在边长为n，m的矩形中选出正方形，每次选出某个正方形的时间为这个正方形的边长，求使用时间最小

题解：可能由于数据比较水一个while模拟就过了
设矩形的边长为x,y，且保证短的边为x，长的边为y
每次选择正方形的边长都为x，每次需要花费的时间都为4*x，选完后原来长为y的边就变成了y-x。因为这个while循环的是用于判断矩形的，所以当遇到边长x=y时，也就是构成正方形时就可以跳出循环了。

#pragma GCC optimize(2) #include <bits/stdc++.h> #define ll long long #define endl  'n' using namespace std; const int MAX=1e6+7;  ll a[MAX],sum[MAX]; int main() {   ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t; cin>>t; while(t--) {    ll x,y,ans=0;    cin>>x>>y; if(x>y)swap(x,y); if(x==y)cout<<x*4<<endl; else if(x==1){     cout<<4*y<<endl; } else {    ans+=x*4; while(y!=x) {     y=y-x; if(x>y)swap(x,y);     ans+=x*4; }    cout<<ans<<endl; } } } 

D.最大收益
题意：有n堆食物，品尝第i堆食物的价值为a[i]，规定不能品尝相邻的两种食物，求最大可获得的价值

题解:这就是一道裸最大不相邻和，个人感觉是最简单的dp类型了
dp[i]=max(dp[i-1],dp[i-2]+a[i]) 注意的是需要预处理一下dp[0]，和dp[1]。
核心思想：假设某一点i，那么可供它选择的方案就有和相邻dp[i-1]项相同，或选择dp[i-2]+a[i]，每次max贪心选最大。

#pragma GCC optimize(2) #include <bits/stdc++.h> #define ll long long #define endl  'n' using namespace std; const int MAX=1e3+7;  ll a[MAX],dp[MAX]; int main() {   ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t;cin>>t; while(t--) {    ll n;cin>>n;    ll ans1=0,ans2=0; for(ll i=0;i<n;i++) {      cin>>a[i];dp[i]=0; }   dp[0]=a[0];   dp[1]=max(dp[0],a[1]); for(ll i=2;i<n;i++) {     dp[i]=max(dp[i-1],dp[i-2]+a[i]); }    cout<<dp[n-1]<<endl; } } 

E.分水果
发现洛谷有一道题背景不同但做法一模一样的原题
洛谷 P6364

题意：n个人排成一列，要求每个人发若干个水果，使得相邻的两个人中分数高的橘子更多，若相同，则两人拿的橘子一样多。求最少需要分多少水果。

题解：预处理每个都为1，先求正着的不降子序列，后再求一次反着的不降子序列，后累加出ans输出即可。

#pragma GCC optimize(2) #include <bits/stdc++.h> #define ll long long #define endl  'n' using namespace std; const int MAX=1e5+7; ll a[MAX],t[MAX]; int main() {   ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int T;cin>>T; while(T--) {         ll n,ans=0;      cin>>n; for(ll i=1;i<=n;i++){    cin>>a[i];    t[i]=1;//读入，初始化  } for(ll i=2;i<=n;i++)//求正着的不降子序列 { if(a[i]>a[i-1])     t[i]=t[i-1]+1;//给水果数赋值  } for(ll i=n;i>=2;i--)//求反着的不降子序列，并把峰顶的人分到水果取更大值，其余同上  { if(a[i]<a[i-1])     t[i-1]=max(t[i-1],t[i]+1); } for(ll i=1;i<=n;i++)ans+=t[i];//统计    cout<<ans<<endl; } return 0; }