第三届ACM山东省赛F题_Chess_单调DP

简单的单调DP，连队列都用不到

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{
    int s,p;
    bool operator<(const node &c) const
    {
        return p<c.p;
    }
};
vector<node>v[10005];
node q;
int f[10005],S[205];
void work(int x)
{
    if (!v[x].size())
    {
        f[x]=0;
        return ;
    }
    int i=0,n=0,now=0;
    while (i<v[x].size())
    {
        while (now<v[x].size() && v[x][now].s==v[x][i].s)
            ++now;
        if (!v[x][i].s)
        {
            S[n++]=now-i;
            if (now-i>=3)
                S[n-1]*=2;
        }
        else
            S[n++]=i-now;
        i=now;
    }
    now=S[0];
    int ans=max(0,now);
    for (i=1; i<n; ++i)
    {
        now=max(now,0)+S[i];
        ans=max(ans,now);
    }
    f[x]=ans;
}
int main()
{
    int T,i,n,m,t,s,p;
    scanf("%d",&T);
    for (int kcase=1; kcase<=T; ++kcase)
    {
        for (i=1; i<=10000; ++i)
            v[i].clear();
        scanf("%d%d",&n,&m);
        int maxt=0,ans=0;
        for (i=0; i<n; ++i)
        {
            scanf("%d%d%d",&t,&s,&p);
            maxt=max(maxt,t);
            q.s=s,q.p=p;
            v[t].push_back(q);
        }
        for (i=1; i<=maxt; ++i)
            sort(v[i].begin(),v[i].end());
        if (maxt<=m+1)
        {
            for (i=1; i<=maxt; ++i)
                work(i),ans=max(ans,f[i]);
            printf("Case %d: %d\n",kcase,ans);
            continue;
        }
        for (i=1; i<=m; ++i)
            work(i),ans=max(ans,f[i]);
        int Q=0;
        for (; i<=maxt; ++i)
        {
            work(i);
            f[i]+=Q;
            ans=max(ans,f[i]);
            Q=max(Q,f[i-m]);
        }
//        for (i=1; i<=maxt; ++i)
//            printf("%d==========%d\n",i,f[i]);
        printf("Case %d: %d\n",kcase,ans);
    }
    return 0;
}