洛谷1315 观光公交
原题链接
交题记录
第一次10 傻了
第二次AC
题解
思路就是基本的大%你大模拟+一点dp,具体看代码
d题目里的
shang这个点上车人中最大的T
xia这个点下车人数
设(reach[i])表示到达i的时间,每次更新,
(reach[i]=max(reach[i-1],shang[i-1])+d[i-1])
f[i]这条边--的收益
Code
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define rep(a,b,c) for(rg ll a=b;a<=c;a++)
#define drep(a,b,c) for(rg ll a=b;a>=c;a--)
#define erep(a,b) for(rg ll a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=1010,maxm=10010;
int n,m,k,d[maxn],shang[maxn],xia[maxn],reach[maxn],f[maxn];
int main(){
n=gi(),m=gi(),k=gi();
rep(i,1,n-1)d[i]=gi();
int t,a,b,ans=0;
rep(i,1,m){
t=gi(),a=gi(),b=gi();
++xia[b],shang[a]=max(shang[a],t);
ans-=t;
}
rep(i,2,n)reach[i]=max(shang[i-1],reach[i-1])+d[i-1];
while(k--){
drep(i,n,2)
if(d[i-1]==0)f[i-1]=0;
else{
f[i-1]=xia[i];
if(reach[i]>shang[i])f[i-1]+=f[i];
}
int res=0;
rep(i,1,n-1)if(f[i]>f[res])res=i;
if(res==-1)break;
--d[res];
rep(i,res+1,n)reach[i]=max(shang[i-1],reach[i-1])+d[i-1];
}
rep(i,1,n)ans+=xia[i]*reach[i];
printf("%d
",ans);
return 0;
}