ZJU/ZOJ 1409 Communication System 解题报告

给出从第i(1<=i<=n)点到第i+1点的m条道路的带宽、价格，求流量/费用的的最大值。流量=min{所选道路带宽}，费用=∑{所选带路价格}。

不难的DP。状态转移方程是f[i,min(j,b[i,k])]=min(f[i,min(j,b[i,k])],f[i-1,j]+p[i,k]);f[i,j]表示到i点流量是j的最小费用，注意筛选有效状态以及维护j的枚举范围即可。我对这题充满了怨念，建模和主要模块代码Coding都没问题，但min函数史无前例地写成了max函数，而且该死的IDE竟然RPWT一动态查错就崩溃，于是苦苦找了很久才发现这一点……

3004785 2008-07-25 17:11:44 Accepted 1409 FPC 00:00.24 608K IwfWcf