Idol Master

C++(clang++11) 解法, 执行用时: 66ms, 内存消耗: 424K, 提交时间: 2021-05-12 14:34:43

#include <bits/stdc++.h>
#define INF (1<<29)
#define N 605 
#define M 200050
using namespace std;
typedef long long LL;

int head[N],cnt=1,tot,S,T;
int p[N],L[N],a,b,c[N],d;
LL dis[N];
int n,m,k;
LL ans;

inline int rd() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct Edge{ int a,b,v,cost,next; }e[M],id;
inline void add(int a,int b,int v,int cost) {
    if (!a || !b) return ; 
    e[++cnt] = (Edge){ a,b,v,cost,head[a] }, head[a] = cnt;
    e[++cnt] = (Edge){ b,a,0,-cost,head[b] },head[b] = cnt;
}

#define cp e[i].v  
#define B e[i].b  

bool SPFA() {  
    bool flag = false;
    for (int i=1;i<=tot;i++) p[i] = 0, dis[i] = -(1LL<<62);
    dis[S] = 0;
    queue<int> q; q.push(S);  
    while (!q.empty()) {  
        int u = q.front(); q.pop();  
        if (u == T) flag = true;
        for (int i=head[u];i;i=e[i].next)  
            if (cp > 0 && dis[u] + e[i].cost > dis[B]) {  
                dis[B] = dis[u] + e[i].cost;  
                p[B] = i;  
                q.push(B);  
            }   
    }  
    return flag;  
}  

void mcf() {  
    int g = p[T] , flow = INF;  
    while (g) {
        flow = min(flow , e[g].v);  
        g = p[ e[g].a ];  
    }
    g = p[T];  
    while (g) {  
        e[g  ].v -= flow;  
        e[g^1].v += flow;  
        ans += 1LL * e[g].cost * flow;  
        g = p[ e[g].a ];  
    }
}
void solve() {
    for (int i=0;i<=tot;i++) head[i] = 0;
    for (int i=0;i<=cnt;i++) e[i] = id;
    cnt = 1, tot = 0;

    n = rd(), k = rd(), a = rd(), b = rd(), d = n-k+1;
    for (int _=1;_<=n;_++) c[_] = rd();

    S = ++tot, T = ++tot;
    for (int _=0;_<=n;_++) L[_] = ++tot;

    add(S, L[0], b, 0), add(L[d], T, b, 0);

    //x[i]

    for (int i=1;i<=n;i++) {
        int p1 = max(i-k, 0), p2 = min(i, d);
        add(L[p1], L[p2], 1, c[i]);
    }

    //y[i]
    for (int i=0;i<d;i++) add(L[i], L[i+1], b-a, 0);

    ans = 0;
    while (SPFA()) mcf();
    printf("%lld\n",ans);
}

int main() {
    for (int T=rd();T;T--) solve();
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 144ms, 内存消耗: 580K, 提交时间: 2020-06-16 15:41:15

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=310,M=1e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,k,a,b,d[N],st[N],vis[N],s,t,c[N];
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d);	ade(b,a,0,-d);}
inline int spfa(){
	queue<int> q; q.push(s);
	for(int i=0;i<=s;i++)	d[i]=-inf,st[i]=0; d[s]=0;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]) if(flow[i]&&d[to[i]]<d[u]+w[i]){
			d[to[i]]=d[u]+w[i];
			if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
		}
	}
	return d[t]>-inf;
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;	st[x]=1;
	for(int i=head[x];i&&f;i=nex[i]){
		if(flow[i]&&!st[to[i]]&&d[to[i]]==d[x]+w[i]){
			int mi=dfs(to[i],min(flow[i],f));
			flow[i]-=mi,flow[i^1]+=mi,fl+=mi,f-=mi;
		}
	}
	return fl;
}
inline int zkw(){
	int res=0;
	while(spfa())	res+=dfs(s,inf)*d[t];
	return res;
}
inline void solve(){
	cin>>n>>k>>a>>b; tot=1; memset(head,0,sizeof head); t=n+2; s=t+1; int num=n-k+1;
	for(int i=1;i<=n;i++)	cin>>c[i];
	add(s,0,b,0),add(num,t,b,0);
	for(int i=1;i<=n;i++)	add(max(0LL,i-k),min(i,num),1,c[i]);
	for(int i=0;i<num;i++)	add(i,i+1,b-a,0);
	cout<<zkw()<<'\n';
}
signed main(){
	int T; cin>>T; while(T--) solve();
	return 0;
}

详情