P5661 [CSP-J 2019] 公交换乘
就是模拟，注意车票还有使用时间限制，所以在记录坐地铁的时候就要设置时限，如果坐公交车的时间过了所有优惠票那就不能坐，而且也要记录最左边可以用的车票位置
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<stack>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int maxn = 1e5+10;
struct node{
int price,time,used;
}tic[maxn];
int main() {
int n,num=0,summ=0,x=1; //x表示能用的优惠票最左边的位置（滑动窗口左边）
cin>>n;
int op,pri,tim;
for(int i=1;i<=n;i++){
cin>>op>>pri>>tim;
if(op==0){
num++;
tic[num].price=pri;tic[num].time=tim+45;tic[num].used=0;
summ+=pri;
}
else{
bool isok=0; //能不能用优惠票
//优先队列、滑动窗口
int newx=x;
for(int k=x;k<=num;k++){
if(tic[k].time<tim){ //如果该票已过期就改编区间左端点的值
newx=k;
continue;
}
if((tic[k].price>=pri)&&tic[k].used==0){
tic[k].used=1;
isok=1;
break;
}
}
x=newx;
if(isok==0){
summ+=pri;
}
}
}
cout<<summ<<endl;
return 0;
}
P5662 [CSP-J2019] 纪念品
居然是背包。。。
把今天手里的钱当做背包的容量，把商品今天的价格当成它的消耗,把商品明天的价格当做它的价值，一天结束后把总钱数加上今天赚的钱，直接写背包模板即可。
另： 在这道题中，我们可以把商品和钱看成同样的东西，因为题目中说了：可以当天买当天卖，所以不必考虑跨天的买卖，只需考虑当天的即可，
这满足动态规划对于最优化原理和无后效性的要求，可以大胆地购买。
每天选完了之后要选择最优结果，作为第二天的起始
也可以从三维推出来
状态！！！：dp[k]表示手里剩k元现金的时候，明天早上都卖了以后的钱数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<stack>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int maxn = 1e2+10;
//居然是背包。。。
/*
把今天手里的钱当做背包的容量，把商品今天的价格当成它的消耗,把商品明天的价格当做它的价值，一天结束后把总钱数加上今天赚的钱，直接写背包模板即可。
另： 在这道题中，我们可以把商品和钱看成同样的东西，因为题目中说了：可以当天买当天卖，所以不必考虑跨天的买卖，只需考虑当天的即可，
这满足动态规划对于最优化原理和无后效性的要求，可以大胆地购买。
*/
//也可以从三维推出来
//状态！！！：dp[k]表示手里剩k元现金的时候，明天早上都卖了以后的钱数
int dp[maxn*100];
int price[maxn][maxn];
int main() {
int t,n,m;
scanf("%d %d %d",&t,&n,&m);
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++) scanf("%d ",&price[i][j]);
}
int ans=m;
//第一天开始的时候为m
for(int i=1;i<t;i++){
memset(dp,-0x3f,sizeof(dp)); //先把数组赋值为负无穷
//什么都不买，今天早上有ans元，明天早上也是ans元
dp[ans]=ans;
//枚举第j个物品
for(int j=1;j<=n;j++){
for(int k=ans;k>=price[i][j];k--){//手里有k元的时候，去推明天早上的钱
//买一件物品，现金减少，赚一份差价，完全背包倒着循环
dp[k-price[i][j]]=max(dp[k-price[i][j]],dp[k]+price[i+1][j]-price[i][j]);
}
}
int maxx=0;
///找一下明天早上收益最大
for(int j=0;j<=ans;j++) maxx=max(maxx,dp[j]) ;
ans=maxx;
}
printf("%d\n",ans);
return 0;
}
P5663 [CSP-J2019] 加工零件
这道题先找规律，发现是否需要提供原材料和路径长度奇偶有关系，而且只要
程序数>最短程序数%2路径就需要提供
所以实际是最短路算法，但是需要处理的特殊点是，就是孤立的点，spfa就是直接在原点处理
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn=1e5+10;
//这道题先找规律，发现是否需要提供原材料和路径长度奇偶有关系，而且只要
//程序数>最短程序数%2路径就需要提供
int n,m,q,cnt;
int head[maxn],vis[maxn][2];
int dis[maxn][2],que[maxn*10],q2[maxn*10],h,r;
struct node{
int u,v,nex;
}ed[maxn*2];
void adde(int u,int v){ //建边
ed[++cnt].u=u;
ed[cnt].v=v;
ed[cnt].nex=head[u];
head[u]=cnt;
}
void spfa(){
for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=1e9;
dis[1][0]=0;
h=1;r=0;
que[++r]=1;
while(h<=r){
int u=que[h];
int t=q2[h]; //一开始为偶数，因为路径为0
h++;
vis[u][t]=0; //出队要清除标记 所以要记录是奇偶
for(int i=head[u];i;i=ed[i].nex){
int v=ed[i].v;
if(dis[v][0]>dis[u][1]+1){
dis[v][0]=dis[u][1]+1;
if(!vis[v][0]){
vis[v][0]=1;
que[++r]=v;
q2[r]=0; //偶数
}
}
if(dis[v][1]>dis[u][0]+1){
dis[v][1]=dis[u][0]+1;
if(!vis[v][1]){
vis[v][1]=1;
que[++r]=v;
q2[r]=1;
}
}
}
}
return;
}
int main()
{
cin>>n>>m>>q;
while(m--){
int u,v;cin>>u>>v;
adde(u,v);adde(v,u); //双向路
}
spfa();
if(head[1]==0) dis[1][0]=1e9;//若1点没有连接边，则1的偶数路径没有
while(q--){
int u,l;
cin>>u>>l;
if(l>=dis[u][l%2]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}