[数据结构与算法]HRBU_20211122训练

A - Krypton

题意：

你有n元，你打算往游戏里进行充值，游戏中有充值优惠，首次充值达到某个金额时，你就会获得一定的返利，具体见下图，问当你充值n元时，最后你能获得的最多的点券数？

做法：

模拟第一个样例

1. 首充1元，充100次，总计获得110010+8=1008

2. 首充6元和1元，充6元16次，充1元4次，总计获得61610+18+1410+8=1026

3. 首充28元和6元和1元，充28元3次，充6元2次，充1元4次，总计获得28310+28+6210+18+1410+8=1054

4. 首充88元和6元和1元，充88元1次，充6元1次，充1元6次，总计获得88110+58+6110+18+1610+8=1084

5. 首充88元和6元，充881次，充6元2次，总计获得88110+58+6210+18=1076

很明显发现只要暴力模拟这个过程最后输出最大值即可。
状态转移方程为

• max(dp[j],dp[j-a[i]]+b[i])

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int maxn=2020;
int T,n,q;
int a[11]={1,6,28,88,198,328,648};
int b[11]={8,18,28,58,128,198,388};
int dp[maxn];
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<7;i++)
        {
            for(int j=n;j>=a[i];j--)
            {
                dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
            }
        }
        printf("%d\n",10*n+dp[n]);
    }
    return 0;
}

B - Meaningless Sequence

题解推荐：https://www.icode9.com/content-4-753763.html

每日小结：

今天欠了两题，大问题大问题，B还是需要捋捋，就算过了有一些地方也还是没有弄懂，今天先逃会课！！让蒟蒻博主去捋捋，感觉总差点啥，感觉第一题也没有解释明白，明天再补进吧。溜了溜了。