哪个网站做app,一个公司网站备案吗,温州网络学堂,如何查看网站是哪家公司做的?描述 猫和老鼠#xff0c;看过吧#xff1f;猫来了#xff0c;老鼠要躲进洞里。在一条数轴上#xff0c;一共有n个洞#xff0c;位置分别在xi#xff0c;能容纳vi只老鼠。一共有m只老鼠位置分别在Xi#xff0c;要躲进洞里#xff0c;问所有老鼠跑进洞里的距离总和最小是…描述 猫和老鼠看过吧猫来了老鼠要躲进洞里。在一条数轴上一共有n个洞位置分别在xi能容纳vi只老鼠。一共有m只老鼠位置分别在Xi要躲进洞里问所有老鼠跑进洞里的距离总和最小是多少。 输入格式 两个用空格隔开的整数m和n。 这一行m个数字分别表示老鼠的位置 接下来n行每行两个数字分别表示洞的位置和容纳量 输出格式 一个整数表示最小的距离总和。如果无解输出-1 样例输入 4 5
6 2 8 9
3 6
2 1
3 6
4 7
4 7 样例输出 11—————————————————————————— n 500, m 500 的时候可以写费用流 但是要比较好的建图方式nm的建图肯定要挂 #includecstdio
#includecstring
#includealgorithm
#define LL long long
using namespace std;
const int M2e37,inf0x3f3f3f3f;
const LL mx1e15;
int read(){int ans0,f1,cgetchar();while(c0||c9) {if(c-) f-1; cgetchar();}while(c0c9) {ansans*10(c-0); cgetchar();}return ans*f;
}
int n,m,q[M],vis[M];
int N,S,T;
LL ans,d[M];
struct node{int to,next,flow;LL cost;}e[M*M];
int first[M],cnt1,cur[M];
void ins(int a,int b,int flow,LL cost){e[cnt](node){b,first[a],flow,cost}; first[a]cnt;}
void insert(int a,int b,int flow,LL cost){ins(a,b,flow,cost); ins(b,a,0,-cost);}
bool spfa(){for(int iS;iT;i) d[i]mx;int head0,tail1;q[0]T; vis[T]1; d[T]0;while(head!tail){int xq[head]; if(headM) head0;for(int ifirst[x];i;ie[i].next){int nowe[i].to;if(e[i^1].flowd[x]e[i^1].costd[now]){d[now]d[x]e[i^1].cost;if(!vis[now]){if(d[now]d[q[head]]){head--; if(head0) headM; q[head]now;}else{q[tail]now; if(tailM) tail0;}vis[now]1;}} }vis[x]0;}return d[S]mx;
}
int dfs(int x,int a){if(xT||a0)return a;vis[x]1;int flow0,f;for(int icur[x];i;ie[i].next){int nowe[i].to;if(!vis[now]d[x]e[i].costd[now](fdfs(now,min(a,e[i].flow)))0){e[i].flow-f; e[i^1].flowf;anse[i].cost*f; flowf;a-f;if(a0)break;}}vis[x]0;return flow;
}
int x[M];
LL sum;
struct pos{int y,k;}qq[M];
bool cmp(pos a,pos b){return a.yb.y;}
int main()
{nread(); mread();S0; Tnm1;for(int i1;in;i) x[i]read(),insert(S,i,1,0);for(int i1;im;i) qq[i].yread(),qq[i].kread(),sumqq[i].k;if(sumn){printf(-1\n); return 0;}sort(qq1,qq1m,cmp);for(int i1;im;i) insert(in,T,qq[i].k,0);for(int i1;im;i){if(i1) insert(in,in-1,inf,qq[i].y-qq[i-1].y);if(im) insert(in,in1,inf,qq[i1].y-qq[i].y);}for(int i1;in;i){int k11; while(qq[k11].yx[i]k1m) k1;int k2m; while(qq[k2-1].yx[i]k21) k2--;if(qq[k1].yx[i]) insert(i,k1n,1,x[i]-qq[k1].y);if(qq[k2].yx[i]) insert(i,k2n,1,qq[k2].y-x[i]);}while(spfa()){for(int i0;iT;i) cur[i]first[i]; dfs(S,inf);}printf(%lld\n,ans);return 0;
} View Code n 5000, m 5000 的时候就需要dp了 先将洞和老鼠按位置从小到大排一波序 因为老鼠选的洞必然是单调递增的 我们可以考虑dp f【i】【j】表示前i个洞选j只老鼠 转移方程 f【i】【j】f【i-1】【k】k1到j 的距离 然后发现是三方的写法 然后就后面可以用单调队列优化dp降一波复杂度 然后就是n方写法了 这里我们每次可以算一下每只老鼠到 第i个洞的 前缀 队列里扔的就是f【j】前缀数组s【j】就好啦 f【i】q【l】s【i】就好辣 #includecstdio
#includecstring
#includealgorithm
#define LL long long
using namespace std;
const int M5e37;
const LL inf1e15;
int read(){int ans0,f1,cgetchar();while(c0||c9) {if(c-) f-1; cgetchar();}while(c0c9) {ansans*10(c-0); cgetchar();}return ans*f;
}
int l,r,n,m,x[M];
struct pos{int y,k;}e[M];
bool cmp(pos a,pos b){return a.yb.y;}
LL sum,f[M],s[M];
LL pabs(LL x){return x0?x:-x;}
struct node{LL v; int pos;}q[M];
int main()
{nread(); mread();for(int i1;in;i) x[i]read();for(int i1;im;i) e[i].yread(),e[i].kread(),sume[i].k;if(sumn){printf(-1\n); return 0;}sort(x1,x1n);sort(e1,e1m,cmp);for(int i1;in;i) f[i]inf;for(int i1;im;i){l1; r0;for(int j1;jn;j) s[j]s[j-1]pabs(x[j]-e[i].y);for(int j0;jn;j){while(lrq[r].vf[j]-s[j]) r--;while(lr(j-q[l].pos)e[i].k) l;q[r].vf[j]-s[j]; q[r].posj;f[j]q[l].vs[j];}}printf(%lld\n,f[n]);return 0;
} View Code 转载于:https://www.cnblogs.com/lyzuikeai/p/7440311.html
