队列斜率优化的dp问题。
#include<iostream> #include<string> #include<queue> #include<vector> #include<cstdio> #include<cstring> using namespace std; typedef pair<int,int> pii; priority_queue<pii>q; int n,m; int num[10000000]; int f[200][10005]; int u[500];//需求； int d[500];//费用； int qq[200][10005]; int head[2000],tail[2000]; int main() { int n,m,s;//m每月费用 scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) scanf("%d",&u[i]); for(int i=1;i<=n;i++) scanf("%d",&d[i]); qq[0][0]=0; qq[0][1]=0; memset(f,10,sizeof(f)); f[0][0]=0; for(int i=1;i<=n;i++)head[i]=1; for(int i=1;i<=n;i++) for(int j=s;j>=0;j--) { while(qq[i-1][head[i-1]]>j+u[i]&&head[i-1]<tail[i-1]) head[i-1]++; int k=qq[i-1][head[i-1]]; f[i][j]=f[i-1][k]+(j+u[i]-k)*d[i]+m*k; while(f[i][j]+(m-d[i+1])*j<=f[i][qq[i][tail[i]]]+(m-d[i+1])*qq[i][tail[i]]&&head[i]<=tail[i])tail[i]--; qq[i][++tail[i]]=j; } cout<<f[n][0]<<endl; return 0; }
真:费用流版：
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define maxx 200000
using namespace std;
int read()
{
int k;
cin>>k;
return k;
}
struct
{
int y,next,flow;
int v;
}e[100000];
int ans=0;
int len=0;
int lin[1000000];
int re[10000000];
int init(int x,int y,int v,int flow)
{
e[++len].y=y;
e[len].next=lin[x];
e[len].flow=flow;
e[len].v=v;
re[len]=len+1;
lin[x]=len;
e[++len].y=x;
e[len].next=lin[y];
e[len].v=-v;
e[len].flow=0;
re[len]=len-1;
lin[y]=len;
return 0;
}
int n,m,s;
int tot=0;
int map[10000000];
int map1[1000000];
int map2[1000000];
int map3[1000000];
int st,ed;
int a[10000000];
int b[10000000];
void initx()
{
/*
map1 进货；
map2 出货；
map 辅助点1；
map3 复制点 2
*/
n=read();
m=read();
s=read();
st=++tot;
for(int i=1;i<=n;i++){map1[i]=++tot;}
for(int i=1;i<=n;i++){map2[i]=++tot;map[i]=++tot;}
for(int i=1;i<=n;i++)map3[i]=++tot;
for(int i=1;i<=n;i++){a[i]=read();}
for(int i=1;i<=n;i++)b[i]=read();
ed=++tot;
for(int i=1;i<=n;i++)
{
init(st,map1[i],b[i],maxx);
init(map1[i],map2[i],0,maxx);
init(map2[i],ed,0,a[i]);
}
for(int i=1;i<=n-1;i++)
{
init(map1[i],map[i],0,s);
init(map[i],map3[i],m,s);
init(map3[i],map2[i+1],0,s);
if(i+1<=n-1)
init(map3[i],map[i+1],0,s);
}
return ;
}
int q[10000];
int dis[100000];
int vis[100000];
int lastvis[100000];
int lastlen[100000];
int head=0,tail=1;
bool spfa()
{
//cout<<"-----------------------------------"<<endl;
memset(vis,0,sizeof(vis));
memset(dis,10,sizeof(dis));
head=0;tail=1;
vis[st]=1;
q[1]=st;
dis[st]=0;
while(head++<tail)
{
int x=q[head];
/* cout<<"the head it "<<x<<endl;
cout<<"::::::::::::::"<<lin[x]<<"---"<<e[lin[x]].flow<<"++"<<e[lin[x]].y<<endl;
*/vis[x]=0;
for(int i=lin[x];i;i=e[i].next)
{
if(e[i].flow<=0)continue;
int y=e[i].y;
if(dis[x]+e[i].v<dis[y])
{
// cout<<"the new y is "<<y<<endl;
dis[y]=dis[x]+e[i].v;
if(vis[y]==0)q[++tail]=y,vis[y]=1;
lastvis[y]=x;lastlen[y]=i;
}
//else cout<<"the wrong y is"<<y<<endl;
// cout<<"k";
}
}
return dis[ed]!=dis[0];
}
int agu()
{
int dalet=dis[0];
for(int now=ed;now!=st;now=lastvis[now])
{
dalet=min(e[lastlen[now]].flow,dalet);
}
for(int now=ed;now!=st;now=lastvis[now])
{
// cout<<now<<endl;
e[lastlen[now]].flow-=dalet;
e[re[lastlen[now]]].flow+=dalet;
ans+=dalet*e[lastlen[now]].v;
}
}
void costflow()
{
while(spfa())
agu();
cout<<ans<<endl;
}
int main()
{
initx();
costflow();
return 0;
}