Storage Keepers UVA

看到很多人都是选择用两次DP去做的

第一个dp[i, j] ： 前i个人照看前j个物品的最大安全值。

第二个dp[i, j] ： 在得到最大安全值的前提下前i个人照看前j个物品的最少花费

这种做法是我没有想到的，这两种都是是用01背包的解法

第一种对应随便装，不要求恰好装满，第二种对应恰好装满

具体写法见代码

另外还看到了另外一种做法，时间复杂度相对高点，但更好写，利用二分+DP，具体做法是对答案二分，然后判断是否可以达到

另外说下我的思路

状态定义为d(i)(j)(k)表示前i个人防守区间j到k的最少花费，当然在该条件下达到了最大值

状态转移也很好写，遍历区间就行了

然后去看题解，发现我想复杂了，因为所有仓库一样，所以可以让i一直为0

因为这里求出d[3][4][5]其实和答案d[3][0][1]是一样的

这里贴出的是两次DP的做法，加了点注释

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<assert.h>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<sstream>
#include<stack>
#include<queue>
#include<string>
#include<bitset>
#include<algorithm>
#pragma warning(disable:4996)
#define me(s)  memset(s,0,sizeof(s))
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,n) for(int i=(n);i>=0;i--)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long llu;
const int inf = 0x3f3f3f3f;
const int dr[] = { 0, -1, 0, 1, -1, -1, 1, 1 };
const int dc[] = { -1, 0, 1, 0, -1, 1, -1, 1 };
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int maxn = 30 + 5;
int n, m, p[maxn], L, Y;
int d[maxn][3 * maxn];//d[i][j]表示前i个人防守前j个仓库的最优L或者Y
int solve()
{//仓库数量大于0但没人守，L为0，仓库数为0，L为无限大，如果两个都为0结果是inffor (int i = 1; i <= n; i++) d[0][i] = 0;for (int i = 0; i <= m; i++) d[i][0] = inf;for(int i=1;i<=m;i++)for (int j = 1; j <= n; j++) {d[i][j] = d[i - 1][j];for (int s = 0; s < j; s++)                           //每一次的决策是防守连续的几个仓库，因为一个仓库只能被一个人防d[i][j] = max(d[i][j], min(d[i - 1][s], p[i] / (j - s)));      //L值由最小防守值决定}if (d[m][n]) L = d[m][n];else return L = 0, Y = 0;            //如果L最大为0，那就不用保安了//防守值越大，越要花钱，所以反过来初始化就行了for (int i = 1; i <= n; i++) d[0][i] = inf;for (int i = 0; i <= m; i++) d[i][0] = 0;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++) {d[i][j] = d[i - 1][j];for (int s = 0; s < j; s++)if (p[i] / (j - s) >= L) d[i][j] = min(d[i][j], d[i - 1][s] + p[i]); //如果超不过最小防守值，就不符合题意了}return Y = d[m][n];
}
int main()
{while (cin >> n >> m) {if (!n && !m) break;for (int i = 1; i <= m; i++) cin >> p[i];solve();cout << L << ' ' << Y << endl;}
}