刷题链接：
https://www.dotcpp.com/oj/train/1038/
题目一：C题 卡牌
看网上更多的是使用的二分，我是自己模拟的，先用大致的模拟思路写，然后再考虑能不能优化
1.对序列进行从小到大排序后，每次抽出一套牌前几个数总会减小，直到减小为0，然后再对前几个牌数为0的牌进行增加，前几个个数为0的牌肯定是同时增加的
2.不进行优化，每次对序列的前几个已经为0的数加一，每次对序列所有数减一，会导致超时
3.优化（贪心）：就是想办法每次不加一减一，每次减尽可能最多（减去最小的即排序后的第一个），每次加尽可能最多（满足三个条件：1.bi>0 2.m足够前几个均分 3.最多加到第一个不为0的个数 ）
AC代码：
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
int n;
LL m; //注意这个数据范围
const int N=200005;
typedef pair<int,int>PII; //第一维存ai,第二维存下标，便于通过这个下标找对应的bi，就不需要自己写排序函数了
PII a[N];
int b[N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
int data;
scanf("%d",&data);
a[i].first=data;
a[i].second=i;
}
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
sort(a+1,a+n+1); //pair排序默认是按照first进行升序排列的
LL ans=0;
while(true) //m最后不一定为0，可能会有剩余，不适合用于循环结束判断
{
int end=0;
int t=a[1].first; //每次减少尽可能的多，减去数列中最小的
for(int i=1;i<=n;i++)
{
a[i].first-=t;
if(a[i].first==0) end=i;
}
ans+=t;
int minb=b[a[1].second]; //每次加回去尽可能多,前几个为0的同时加，满足三个条件：1.bi>0 2.m足够前几个均分 3.最多加到第一个不为0的数的数据
for(int i=1;i<=end;i++)
{
if(b[a[i].second]<minb) minb=b[a[i].second];
}
if(minb==0) break;
int j=minb;
for(;j>=1;j--)
{
if(m>=end*j) break;
}
if(j==0) break; //有边界情况就要考虑特殊判断一下，所有的ai都一样时
if(end<n) j=j<a[end+1].first?j:a[end+1].first;
for(int i=1;i<=end;i++)
{
if(b[a[i].second]==0)
{
m=0;
break;
}
a[i].first+=j;
b[a[i].second]-=j;
m-=j;
}
}
printf("%lld",ans);
return 0;
}
题目二：D题 最大数字
1.简单的dp问题，因为序列满足局部最优解，前i个数字构成的数最大其实是前i-1个数字构成的最大数加上最大化的第i个数字，前i个数字构成最大数的状态可以从前i-1个数构成最大数转移过来，但是要保存一下对前i-1个数字进行操作用了多少加和减操作
2.dp[i][j][k] 前i个数字最多进行j次加和最多进行k次减得到的最大数，然后考虑最后一步，第i个数字会进行多少次加和减操作，进行一下枚举
#include<iostream>
using namespace std;
typedef long long LL;
int n,A,B;
int num[20];
LL dp[20][105][105];
int Now(int i,int s,int x) //对第i位数字进行s次加和x次减后得到的数字
{
int tmp=num[i]+s-x;
if(tmp<0)
{
tmp=-tmp;
return (10-tmp%10)%10;
}
else return tmp%10;
}
LL Add(LL pre,LL now) //将第i个数字拼到后面
{
return pre*10+now;
}
int main()
{
char h=cin.get();
int ind=1;
while(h!=' ')
{
num[ind++]=h-'0';
h=cin.get();
}
cin>>A>>B;
dp[0][0][0]=0;
dp[1][0][0]=num[1];
int n=ind-1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=A;j++)
{
for(int k=0;k<=B;k++)
{
for(int s=0;s<=j;s++)
{
for(int x=0;x<=k;x++)
{
dp[i][j][k]=max(Add(dp[i-1][j-s][k-x],Now(i,s,x)),dp[i][j][k]);
}
}
}
}
}
cout<<dp[n][A][B]<<endl;
return 0;
}
题目三：E题 出差
简单的单源最短路径，隔离天数和路径天数是同等级别的，直接将到达某个目的地的隔离天数加到路径权值上
int类型的无穷大设置为0x3f3f3f3f (4个)
longlong类型的无穷大设置为0x3f3f3f3f3f3f3f3f（8个）
#include<iostream>
using namespace std;
const int N=1010;
const int INFI=0x3f3f3f3f; //这个记住了，一定要设置为最大的，1e8都不行 ，
int n,m;
int graph[N][N];
int geli[N];
int dist[N];
int visited[N];
int Findmin()
{
int min_i=-1,min=INFI;
for(int i=1;i<=n;i++)
{
if(!visited[i]&&dist[i]<min)
{
min=dist[i];
min_i=i;
}
}
return min_i;
}
void Dijistra(int s)
{
for(int i=1;i<=n;i++)
{
dist[i]=graph[s][i];
}
visited[s]=1;
while(true)
{
int min_i=Findmin();
if(min_i==-1) break;
visited[min_i]=1;
for(int i=1;i<=n;i++)
{
if(!visited[i]&&graph[min_i][i]!=INFI&&dist[min_i]+graph[min_i][i]<dist[i])
{
dist[i]=dist[min_i]+graph[min_i][i];
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>geli[i];
geli[1]=0;
geli[n]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) graph[i][j]=0;
else graph[i][j]=INFI;
}
}
for(int i=0;i<m;i++)
{
int v1,v2,w;cin>>v1>>v2>>w;
if(v1==v2) //要注意考虑自环的情况，这道题多重边的好像没有涉及
{
graph[v1][v2]=0;
graph[v2][v1]=0;
}
else
{
graph[v1][v2]=w+geli[v2];
graph[v2][v1]=w+geli[v1];
}
}
Dijistra(1);
cout<<dist[n];
return 0;
}
题目四：F题 费用报销
简单的0/1背包变题
dp[i]表示前i张票据能凑成的最大费用
题目说的面值尽可能接近M其实就是面值最大
判断最后一个票据能不能要不要，如果不能要：dp[i][j]=dp[i-1][j];
如果能要（必须满足第i张票据的面值小于实际费用），再考虑要了和更大还是不要和更大
并且前一个票据必须与当前票据时间相差大于等于k天 dp[i][j]=max(dp[i][j],dp[h][j-w[num[i]]]+w[num[i]]);
错误思想：求与当前票据相差大于等于k天的所有dp[h][j-w[num[i]]]的最大值，再加上w[num[i]]
只需要从前一个状态转移过来，即dp[j]，j就是前一个状态，j满足与与当前票据时间相差大于等于k天
dp[i]不是看最后一个选的哪一个，而是前个（与最长递增子序列的问题区别开）
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k;
const int N=1005;
int num[N];
int dp[N][5005];
int w[N];
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
int y,d,wi;cin>>y>>d>>wi;
for(int j=1;j<=y-1;j++)
num[i]+=month[j]; //将日期转换为距离1月1日的天数
num[i]+=d;
w[num[i]]=max(w[num[i]],wi); //按照日期存储当天的面值，如果有当天的重复票据，选最大的那个
}
sort(num+1,num+n+1); //将日期从小到大排序
for(int i=1;i<=n;i++)
{
int h=i-1;
while(h>0&&num[i]-num[h]<k) h--; //求与当前票据相差大于等于k天的最后一个状态
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if(w[num[i]]<=j) //第i天的费用没有超过实际费用，可以选择是否要
{
dp[i][j]=max(dp[i][j],dp[h][j-w[num[i]]]+w[num[i]]);
}
}
}
cout<<dp[n][m];
return 0;
}