本文共 2162 字，大约阅读时间需要 7 分钟。

一眼看过去,裸的费用流

把每个时刻拆成一个点,每个菜品作为一个点

每个时刻连向每个菜品,费用为对应的费用

源点连向每个时刻,每个菜品连向汇点.

当然所有流量都是$1$,为了保证所有东西只能使用一次

跑一个最小费用最大流即可.

#include 
   
    using namespace std;const int maxn = 4e5+10;const int inf = 1e9;struct edge{
   	int to,nxt,w,flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int w,int flow){
   	d[++cnt] = (edge){
   v,head[u],w,flow},head[u] = cnt;	d[++cnt] = (edge){
   u,head[v],-w,0},head[v] = cnt;}int FLOW[maxn],pre[maxn],dis[maxn],vis[maxn],n,a[maxn];bool spfa(int s,int t){
   	for(int i=s;i<=t;i++)	dis[i] = inf,vis[i] = 0;	queue
    
     q; q.push( s ); dis[s] = 0,FLOW[s] = inf;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		vis[u] = 0;		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( dis[v]>dis[u]+d[i].w&&d[i].flow )			{
   				dis[v]=dis[u]+d[i].w;				FLOW[v] = min( FLOW[u],d[i].flow );				pre[v]  = i;				if( !vis[v] )	vis[v] = 1,q.push( v );			}		}	}	return dis[t]!=inf;}int MCMF(int s,int t){
   	int maxcost=0;	while( spfa(s,t) )	{
   		maxcost += FLOW[t]*dis[t];		int x = t, i;		while( x!=s )		{
   			i = pre[x];			d[i].flow-=FLOW[t], d[i^1].flow+=FLOW[t];			x = d[i^1].to;		}	}	return maxcost;}int main(){
   	int T; cin >> T;	while( T-- )	{
   		cin >> n;		int s = 0,t = 400+n+1;		for(int i=1;i<=n;i++)	cin >> a[i],add(i+400,t,0,1);		for(int i=1;i<=400;i++)		{
   			add(s,i,0,1);			for(int j=1;j<=n;j++)				add( i,400+j,abs(i-a[j]),1 );		}		cout << MCMF(s,t) << endl;		cnt = 1;		for(int i=s;i<=t;i++)	head[i] = 0;	}}
    
   

但是用dp也很简单

然而一眼看到是费用流就想不出其他做法了hhh…

定义$f[i][j]$为前$i$个时间拿了前$j$个菜品的最小代价

因为不可能空出中间某个菜不拿而去拿后面的

这样即使拿的那个减小了花费,中间那个菜也会增加花费,肯定不会更划算.

想到这个就傻瓜式转移即可

#include 
   
    using namespace std;const int maxn = 209;const int inf = 1e9;int t,n,a[maxn],f[maxn<<1][maxn];int main(){
   	cin >> t;	while( t-- )	{
   		cin >> n;		for(int i=1;i<=n;i++)	cin >> a[i];		sort( a+1,a+1+n );		int ans = inf;		memset( f,20,sizeof f);		f[0][0] = 0;		for(int i=1;i<=400;i++)		{
   			f[i][0] = 0;			int limit = min( i,n );			for(int j=1;j<=limit;j++)				{
   				f[i][j] = min( f[i-1][j],f[i-1][j-1]+abs(i-a[j]) );				if( j==n )	ans = min( ans,f[i][j] );			}		}		cout << ans << endl;	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110176937 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！