思路：
1.DP
f[i][j]表示第i个月的月底 还剩j的容量
转移还是相对比较好想的……
f[i][j+1]=min(f[i][j+1],f[i][j]+d[i]);
if(j>=u[i+1])f[i+1][j-u[i+1]]=min(f[i+1][j-u[i+1]],f[i][j]+m*j);
else f[i+1][0]=min(f[i+1][0],f[i][j]+d[i+1]*(u[i+1]-j)+m*j);//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,u[55],d[55],f[55][10005];
int main(){
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]);
memset(f,0x3f,sizeof(f));
f[1][0]=d[1]*u[1];
for(int i=1;i<=n;i++)
for(int j=0;j<=s;j++){
f[i][j+1]=min(f[i][j+1],f[i][j]+d[i]);
if(j>=u[i+1])f[i+1][j-u[i+1]]=min(f[i+1][j-u[i+1]],f[i][j]+m*j);
else f[i+1][0]=min(f[i+1][0],f[i][j]+d[i+1]*(u[i+1]-j)+m*j);
}
printf("%d
",f[n][0]);
}
2.
费用流 裸的建图吧
源->i 流量inf 费用d[i]
i->汇 流量u[i] 费用0
i->i+1 （i!=n） 流量S 费用m
跑一哈 搞定~
//By SiriusRen
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 55
#define M 55555
#define inf 0x3f3f3f3f
#define mem(x,y) memset(x,y,sizeof(x))
int n,m,S,xx,T,edge[M],v[M],cost[M],first[N],nxt[M],vis[N],minn[N],d[N],with[N],tot,ans;
void Add(int x,int y,int C,int E){edge[tot]=E,cost[tot]=C,v[tot]=y,nxt[tot]=first[x],first[x]=tot++;}
void add(int x,int y,int C,int E){Add(x,y,C,E),Add(y,x,-C,0);}
bool tell(){
mem(vis,0),mem(with,0),mem(d,0x3f),mem(minn,0x3f);
queue<int>q;q.push(0),d[0]=0;
while(!q.empty()){
int t=q.front();q.pop();vis[t]=0;
for(int i=first[t];~i;i=nxt[i])
if(d[v[i]]>d[t]+cost[i]&&edge[i]){
with[v[i]]=i,d[v[i]]=d[t]+cost[i],minn[v[i]]=min(minn[t],edge[i]);
if(!vis[v[i]])vis[v[i]]=1,q.push(v[i]);
}
}return d[T]!=0x3f3f3f3f;
}
int zeng(){
for(int i=T;i;i=v[with[i]^1])
edge[with[i]]-=minn[T],edge[with[i]^1]+=minn[T];
return minn[T]*d[T];
}
int main(){
mem(first,-1);
scanf("%d%d%d",&n,&m,&S),T=n+1;
for(int i=1;i<=n;i++)scanf("%d",&xx),add(i,T,0,xx);
for(int i=1;i<=n;i++){
scanf("%d",&xx),add(0,i,xx,inf);
if(i!=n)add(i,i+1,m,S);
}
while(tell())ans+=zeng();
printf("%d
",ans);
}
这道题 费用流还是要稍微快一点儿的……