先放个链接
[NOIP2011 提高组]观光公交

蒟蒻想到了一个dp方程，但提交后只a了前两个k=0的点和hack数据，不知道是自己实现有问题还是dp方程错了

定义$f(i,j)$为到达第$i$个景区且用了$j$加速器时，仅考虑目的地为前$i$个景区的人的用时之和的最小值. $pret(i)$表示目的地为第i个景区的所有人最开始来到景点的时间$T$之和，$cnt(i)$为目的地为$i$的人数，$t(i,j)$为$f(i,j)$取最优解时的公交所花的时间，$hou(i)$为最开始在第$i$个景区的人的最晚时刻

dp方程

$f(i,j)=\min_{j-D_{i-1}\leq p \leq j}(f(i-1,p)+cnt(i)*[\max(t(i-1,p),hou(i-1))+D_{i-1}-j+p]-pret(i))$

这个dp方程可以使用单调队列优化，对于上面方程中$f(i,j)$的$t(i,j)$ 其由最优转移点pos得到：

$t(i,j)=\max(t(i-1,pos),hou(i-1))+D_{i-1}-j+pos$

我的错误代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ri register int
using ll=long long;
using namespace std;
int n,m,k;
int d[1005],sum[1005],cnt[1005],hou[1005],t[2][100005],pret[1005];ll f[2][100005];//蒟蒻学艺不精  只会用奇偶性交替的滚动数组
inline ll cal(int p,int i){return f[(i-1)&1][p]+cnt[i]*(max(t[(i-1)&1][p],hou[i-1])+p);}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    memset(f,0x3f,sizeof(f));
    for(ri i=1;i<n;++i){
        cin>>d[i];
        sum[i]=sum[i-1]+d[i];
    }
    for(ri i=1;i<=m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        pret[c]+=a;
        hou[b]=max(hou[b],a);
        ++cnt[c];
    }
    f[0][0]=0;
    for(ri i=1;i<=n;++i){
        deque<int>q;
        int pre=-pret[i]+cnt[i]*d[i-1];//提出与p无关的项到min外面
        for(ri j=0;j<=k&&j<=sum[i-1];++j){
            int tmp=f[(i-1)&1][j]+cnt[i]*(max(t[(i-1)&1][j],hou[i-1])+j);
            int delta=-cnt[i]*j;//进一步提出与p无关的项到min外面
            while(!q.empty()&&q.front()<max(j-d[i-1],0))q.pop_front();
            while(!q.empty()&&cal(q.back(),i)>=tmp)q.pop_back();
            q.push_back(j);
            int pos=q.front();
            int ans=f[(i-1)&1][pos]+cnt[i]*(max(t[(i-1)&1][pos],hou[i-1])+pos);
            f[i&1][j]=pre+delta+ans;
            t[i&1][j]=max(t[(i-1)&1][pos],hou[i-1])+d[i-1]-j+pos;
        }
    }
    cout<<f[n&1][k];
    return 0;
}

蒟蒻一直不擅长dp，想借这个理错的机会好好加深对dp的理解，毕竟看出这个题目为什么不能用dp也是对dp的一种把握.

谢谢各位神犇的鼎力相助www