怎么题解都是用费用流做的啊。。。用单调队列多优美啊。
题意:某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。
首先这道题和经典的汽车加油问题差不多，那道题可以用单调队列做，然而这道题也是可以的。
此题唯一的难点在于存储费用m，也就是放在仓库里每件产品每个月多加m元，而这个产品的费用实际上只取决与什么时候拿出来。
我们可以在读入di的时候，让di变成di-(i-1)*m,这样每件产品就只和它取出来的时间有关系，而这个关系显然是单调的。
那么我们类似于经典问题，使仓库一直处于满货的状态，如果要加货，就把比新加的货物价值高的给拿出来。这样贪心的选择用单调队列维护。
可以达到O(n),而这道题的n<=50,不得不说数据是真的太弱了，是为了方便费用流？
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <bitset> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-8 # define MOD 100000000 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N=55; //Code begin... struct Qnode{int cost, num;}que[N]; int U[N], D[N], head, tail; int main () { int n, m, S, ans=0, V=0; scanf("%d%d%d",&n,&m,&S); FOR(i,1,n) scanf("%d",U+i); FOR(i,1,n) scanf("%d",D+i), D[i]-=(i-1)*m; head=0; tail=-1; FOR(i,1,n) { while (head<=tail&&que[tail].cost>=D[i]) V-=que[tail].num, --tail; while (head<=tail&&que[head].num<=U[i]) { ans+=(que[head].cost+(i-1)*m)*que[head].num; V-=que[head].num; U[i]-=que[head].num; ++head; } if (head<=tail) ans+=(que[head].cost+(i-1)*m)*U[i], V-=U[i], que[head].num-=U[i]; else ans+=(D[i]+(i-1)*m)*U[i]; que[++tail].cost=D[i]; que[tail].num=S-V; V=S; } printf("%d ",ans); return 0; }