论坛的网站开发项目,备案网站域名和主机关系,企业推广方式知名隐迅推,做网站和推广找哪家好题目
n(n500)种球#xff0c;第i种有ai(0ai1e12)个球#xff0c;
m(m5e5)个盒子#xff0c;第j个能放bj(0bj1e12)个球
特别地#xff0c;第j个盒子最多能放i*j个第i种球
求m个盒子能放的最多的球的总数
思路来源
官方题解
题解 显然是一个最…题目
n(n500)种球第i种有ai(0ai1e12)个球
m(m5e5)个盒子第j个能放bj(0bj1e12)个球
特别地第j个盒子最多能放i*j个第i种球
求m个盒子能放的最多的球的总数
思路来源
官方题解
题解 显然是一个最大流模型超级源点s到超级汇点的流量t
由于最小割最大流可以考虑最后这个图割完之后长什么样 比如左侧1、3记为集合P含于S右侧点2记为集合Q含于S
那么记左侧集合非P含于T右侧集合非Q含于T
那么最小割的边集的构成由三部分组成
1. 超级源点s与集合非P之间的边即左侧属于t的点断开与s的边
2. 集合Q与超级汇点t之间的边即右侧属于s的点断开与t的边
3. 左侧集合P与右侧集合非Q之间的边左侧属于s的点右侧属于t的点断开左右点之间的边 由于边是有向的
所以无需断开左侧属于t的点和右侧属于s的点之间的边
因为从上游流量就已经切断了 然后就是对官方题解的一些补充说明吧 最小割的代价由三部分组成
形如
所以枚举也就是左侧属于S集合的i之和
这样可以通过dpO(n^3)求得
也就是属于S集合i之和固定时不属于S集合的Ai之和的最小值 而后面两坨k固定时答案之和j有关
可以任意划分将一部分划给S集合另一部分划给T集合
并且划给S集合的每个点贡献是j*k划给T集合的每个点贡献是B[j]
使得这两部分之和最小那么考虑某一个点自然是哪个小划给哪边
所以每个点贡献是min(j*k,B[j]) 由j*kB[j]解得kB[j]/j所以枚举k的时候每个点从S换到T的操作只会发生一次
记录一下这个翻转的时机即可一边枚举k一边实现对贡献的统计
这部分复杂度O(n^2m) 总复杂度O(n^3n^2m)
代码
#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define scll(a) scanf(%lld,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N505,M5e510,SN*(N1)/2;
const ll INF0x3f3f3f3f3f3f3f3fll;
int n,m;
ll a[N],b[M],dp[N][S],ans,sum,sum2;
vectorintflip[S];
void upd(ll x,ll y){xmin(x,y);
}
int main(){sci(n),sci(m);rep(i,1,n)scll(a[i]);rep(i,1,m)scll(b[i]);memset(dp,INF,sizeof dp);dp[0][0]0;rep(i,0,n-1){int upi*(i1)/2,vi1;rep(j,0,up){upd(dp[i1][jv],dp[i][j]);upd(dp[i1][j],dp[i][j]a[i1]);}}int limn*(n1)/2;rep(j,1,m){//先认为都是j*k再翻到b[j]ll vb[j]/j;if(vlim)flip[v].pb(j);sumj;}ans8e18;rep(j,0,lim){ansmin(ans,dp[n][j]1ll*sum*jsum2);for(auto v:flip[j]){sum-v;sum2b[v];}}printf(%lld\n,ans);return 0;
}
