思路：
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#include #include 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\n",f[n][0]);}
2.
费用流 裸的建图吧 源->i 流量inf 费用d[i] i->汇 流量u[i] 费用0 i->i+1 （i!=n） 流量S 费用m跑一哈 搞定~
//By SiriusRen#include#include #include 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 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\n",ans);}
