请问您要来点兔子吗？

C++(g++ 7.5.0) 解法, 执行用时: 95ms, 内存消耗: 560K, 提交时间: 2022-10-05 03:17:23

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
namespace dinic
{
	const int N=505;
	const int inf=1e18;
	
	int S,T,MAXn;
	int v[N],dis[N],lst[N];
	struct node{int to,val,w,rev;};
	vector <node> e[N];
	void add(int x,int y,int z,int w)
	{
		e[x].push_back((node){y,z,w,(int)e[y].size()});
		e[y].push_back((node){x,0,-w,(int)e[x].size()-1});
	}
	
	bool SPFA()
	{
		for(int i=0;i<=MAXn;++i)dis[i]=inf , lst[i]=v[i]=0;
		//memset(lst,0,sizeof(lst));
		//for(int i=0;i<N;i++) dis[i]=inf;
		queue <int> q;dis[S]=0,v[S]=1,q.push(S);
		while(q.size())
		{
			int x=q.front();q.pop(),v[x]=0;
			for(const auto &i:e[x]) if(dis[i.to]>dis[x]+i.w&&i.val>0)
			{
				dis[i.to]=dis[x]+i.w;
				if(!v[i.to]) v[i.to]=1,q.push(i.to); 
			}
		}
		return dis[T]!=inf;
	}
	int dfs(int x,int flow)
	{
		if(x==T) return flow;int sum=0;v[x]=1;
		for(int &i=lst[x];i<e[x].size();i++)
		{
			int t=e[x][i].to,val=e[x][i].val,w=e[x][i].w,r=e[x][i].rev;
			if(dis[t]!=dis[x]+w||val<=0||v[t]) continue;
			int Q=dfs(t,min(flow,val));
			sum+=Q,flow-=Q,e[x][i].val-=Q,e[t][r].val+=Q;
			if(!flow) break;
		}
		v[x]=0;if(!sum) dis[x]=inf;return sum;
	}
	pii FYL()
	{
		int ans1=0,ans2=0;
		while(SPFA()){int x=dfs(S,inf);ans1+=x,ans2+=x*dis[T];}
		return {ans1,ans2};
	}
	
	/*int n,m;
	void MUBAN()
	{
		scanf("%lld%lld",&n,&m);
		S=1 , T=n , MAXn=n;
		for(int i=1;i<=m;i++)
		{
			int x,y,z,w;
			scanf("%lld%lld%lld%lld",&x,&y,&z,&w);
			add(x,y,z,w);
		}
		pii ans=FYL();
		printf("%lld %lld",ans.first,ans.second);
	}*/
	
	int n;
	int k,L,R;
	int a[N];
	void init()
	{	
		scanf("%lld",&n);
		for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
		scanf("%lld%lld%lld",&k,&L,&R);
		
		for(int u=0;u<=MAXn;++u)e[u].clear();
		S=n+1 , T=S+1 , MAXn=T;
	}
	void Build()
	{
		add(S,1,R,-0);// , add(n,T,inf,-0);
		//for(int u=1;u<n;++u)add(u,u+1,R-L,-0);
		add(n,T,R-L,-0);
		for(int u=1;u<n;++u)
		{
			if(u<k)add(u,u+1,inf,-0);
			else add(u,u+1,R-L,-0);
		}
		
		for(int u=1;u<=n;++u)
		{
			int v = (u+k<=n) ? u+k : T;
			add(u,v,1,-a[u]);
		}
	}
	void work()//最大费用最大流 
	{
		init();
		Build();
	    pii res=FYL();
	    printf("%lld\n",-res.second);
	}
}
signed main()
{
	int TTT;scanf("%lld",&TTT);while(TTT--)dinic::work();
	return 0;
}

C++(clang++11) 解法, 执行用时: 149ms, 内存消耗: 784K, 提交时间: 2020-12-18 11:37:18

#include <bits/stdc++.h>

using namespace std;

#define N 505
#define INF 1000000009

int n,K,L,R,l=1,S,T;
int to[N<<2],h[N<<2],s[N],c[N<<2],w[N<<2],a[N],dist[N],mn[N],pre[N],vis[N];

struct node {
    int x;
    bool friend operator < (node A,node B){
        return dist[A.x]>dist[B.x];
    }
}p;

priority_queue<node >Q;

void hah(int x,int y,int z,int t){
    to[++l]=y,h[l]=s[x],s[x]=l,c[l]=z,w[l]=t;
    to[++l]=x,h[l]=s[y],s[y]=l,c[l]=-z,w[l]=0;
}
bool SPFA(){
    for(int i=1;i<=n+2;i++)mn[i]=dist[i]=INF;
    dist[S]=0;
    Q.push({S});
    while(!Q.empty()){
        p=Q.top();
        Q.pop();
        vis[p.x]=0;
        for(int i=s[p.x];i;i=h[i]){
            if(w[i] && dist[to[i]]>dist[p.x]+c[i]){
                dist[to[i]]=dist[p.x]+c[i];
                mn[to[i]]=min(mn[p.x],w[i]);
                pre[to[i]]=i;
                if(!vis[to[i]]){
                    Q.push({to[i]});
                    vis[to[i]]=1;
                }
            }
        }
    }
    if(dist[T]==INF)return false;
    else return true;
}
int MCMF(){
    int ans=0;
    while(SPFA()){
        int x=T;
        while(x!=S){
            int tmp=pre[x];
            w[tmp]-=mn[T];
            w[tmp^1]+=mn[T];
            x=to[tmp^1];
        }
        ans+=dist[T]*mn[T];
    }
    return ans*(-1);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        l=1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        scanf("%d%d%d",&K,&L,&R);
        S=n+2,T=n+1;
        hah(S,1,0,R);
        for(int i=1;i<=n;i++){
            if(i<K)hah(i,i+1,0,INF);
            else hah(i,i+1,0,R-L);
            hah(i,min(i+K,T),-a[i],1);
        }
        printf("%d\n",MCMF());
        for(int i=1;i<=n+2;i++)s[i]=0;
    }
}

详情