这题也太水了吧？

再也不做GOLD的题了，去玩PLATINUM了拜拜。

T1裸分层图最短路。

T2裸容斥。

T3更SB的DP。

代码

T1

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;

using std::cin;
using std::cout;
using std::endl;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN=50005;
const int MAXM=100005;

int n,m,k,ecnt,head[MAXN<<1];
LL dis[MAXN<<1];
bool book[MAXN<<1];

struct Edge{
    int to,nxt,w;
}e[MAXM*4+MAXN];

inline void add_edge(int bg,int ed,int val){
    ++ecnt;
    e[ecnt].to=ed;
    e[ecnt].nxt=head[bg];
    e[ecnt].w=val;
    head[bg]=ecnt;
}

std::queue<int> q;

void spfa(){
    while(!q.empty()) q.pop();
    memset(dis,0x3f,sizeof dis);
    dis[n]=0;
    q.push(n);
    book[n]=true;
    while(!q.empty()){
        int x=q.front();
        trav(i,x){
            int ver=e[i].to;
            if(dis[ver]>dis[x]+e[i].w){
                dis[ver]=dis[x]+e[i].w;
                if(!book[ver]){
                    q.push(ver);
                    book[ver]=true;
                }
            }
        }
        q.pop();
        book[x]=false;
    }
}

int main(){
    n=read(),m=read(),k=read();
    rin(i,1,m){
        int u=read(),v=read(),w=read();
        add_edge(u,v,w);
        add_edge(v,u,w);
        add_edge(u+n,v+n,w);
        add_edge(v+n,u+n,w);
    }
    rin(i,1,k){
        int x=read(),y=read();
        add_edge(x,x+n,-y);
    }
    spfa();
    rin(i,1,n-1){
        if(dis[n+i]<=dis[i]) printf("1\n");
        else printf("0\n");
    }
    return 0;
}

T2

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;

using std::cin;
using std::cout;
using std::endl;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

typedef std::pair<int,int> tw;
typedef std::pair<int,tw> tr;
typedef std::pair<tw,tw> fo;
typedef std::pair<tw,tr> fi;

inline tw mktw(int x,int y){
    return (tw){x,y};
}

inline tr mktr(int x,int y,int z){
    return (tr){x,mktw(y,z)};
}

inline fo mkfo(int x,int y,int z,int v){
    return (fo){mktw(x,y),mktw(z,v)};
}

inline fi mkfi(int x,int y,int z,int v,int w){
    return (fi){mktw(x,y),mktr(z,v,w)};
}

int n;
int mp1[1000005];
std::map<tw,int> mp2;
std::map<tr,int> mp3;
std::map<fo,int> mp4;
std::map<fi,int> mp5;

int main(){
    n=read();
    rin(i,1,n){
        int a[6];
        a[1]=read(),a[2]=read(),a[3]=read(),a[4]=read(),a[5]=read();
        std::sort(a+1,a+6);
        int x=a[1],y=a[2],z=a[3],v=a[4],w=a[5];
        ++mp1[x];
        ++mp1[y];
        ++mp1[z];
        ++mp1[v];
        ++mp1[w];
        ++mp2[mktw(x,y)];
        ++mp2[mktw(x,z)];
        ++mp2[mktw(x,v)];
        ++mp2[mktw(x,w)];
        ++mp2[mktw(y,z)];
        ++mp2[mktw(y,v)];
        ++mp2[mktw(y,w)];
        ++mp2[mktw(z,v)];
        ++mp2[mktw(z,w)];
        ++mp2[mktw(v,w)];
        ++mp3[mktr(x,y,z)];
        ++mp3[mktr(x,y,v)];
        ++mp3[mktr(x,y,w)];
        ++mp3[mktr(x,z,v)];
        ++mp3[mktr(x,z,w)];
        ++mp3[mktr(x,v,w)];
        ++mp3[mktr(y,z,v)];
        ++mp3[mktr(y,z,w)];
        ++mp3[mktr(y,v,w)];
        ++mp3[mktr(z,v,w)];
        ++mp4[mkfo(x,y,z,v)];
        ++mp4[mkfo(x,y,z,w)];
        ++mp4[mkfo(x,y,v,w)];
        ++mp4[mkfo(x,z,v,w)];
        ++mp4[mkfo(y,z,v,w)];
        ++mp5[mkfi(x,y,z,v,w)];
    }
    LL ans=0;
    rin(i,1,1000000) ans+=1ll*mp1[i]*(mp1[i]-1)/2;
    for(register std::map<tw,int>::iterator it=mp2.begin();it!=mp2.end();++it) ans-=1ll*it->second*(it->second-1)/2;
    for(register std::map<tr,int>::iterator it=mp3.begin();it!=mp3.end();++it) ans+=1ll*it->second*(it->second-1)/2;
    for(register std::map<fo,int>::iterator it=mp4.begin();it!=mp4.end();++it) ans-=1ll*it->second*(it->second-1)/2;
    for(register std::map<fi,int>::iterator it=mp5.begin();it!=mp5.end();++it) ans+=1ll*it->second*(it->second-1)/2;
    printf("%lld\n",1ll*n*(n-1)/2-ans);
    return 0;
}

T3

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;

using std::cin;
using std::cout;
using std::endl;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN=10005;
const int MAXK=1005;

int n,k,a[MAXN],f[MAXN];

int main(){
    n=read(),k=read();
    rin(i,1,n) a[i]=read();
    f[0]=0;
    rin(i,1,n){
        int temp=0;
        irin(j,i,std::max(i-k+1,1)){
            temp=std::max(temp,a[j]);
            f[i]=std::max(f[i],f[j-1]+temp*(i-j+1));
        }
    }
    printf("%d\n",f[n]);
    return 0;
}