CF815C的空间优化
Euler_Pursuer
2018-10-12 11:27:24
题目很简单，但是想优化却不容易。
我们可以很明显的列出DP方程，也就是考虑某个优惠券是否使用来转移状态。它使用了，那么依赖它的优惠券可使用可不使用；它没使用，那么依赖它的优惠券就不能使用。参考@[feng_chengjie](https://www.luogu.org/space/show?uid=36294) 的题解，设dp[u][j][0/1]是以u为根子树中,u用或者不用优惠券时,选j件物品需要的最小代价DP方程：
$$dp[u][sum][1]=\min(dp[u][sum][1],dp[u][i][1]+dp[son][sum-i][1])$$
$$dp[u][sum][1]=\min(dp[u][sum][1],dp[u][i][1]+dp[son][sum-i][0])$$
$$dp[u][sum][0]=\min(dp[u][sum][0],dp[u][i][0]+dp[son][sum-i][0])$$
通过枚举一个节点的儿子，转移方程即可。
但是我们发现它的空间复杂度为$O(n^2)$，而且在转移的过程中，某个节点转移完毕之后其DP数组是没用的，也就是这样浪费了很多空间。所以我们可以考虑对某个儿子DP完毕之后，释放掉该儿子占用的空间，我们可以用vector实现。
考虑其空间复杂度的最坏情况，注意到我们每次都是在DP完子树之后才对该节点扩充空间，也就是说每个节点至少要有两个儿子才能对空间产生一定的“浪费”，而每次扩充的空间都是该节点前面的子树的大小，对于当前儿子来说，它扩充的空间又是它的当前考虑的儿子的左兄弟，而我们上述考虑的节点均互不相同，因此累积起来空间复杂度为$O(n)$。当然，vector可能有点小常数，但是实际测试中时间会比优化前更快。
对于vector的释放空间的操作，不是什么clear就能解决的事。因为clear看上去空间清空了，实际上指针还在，你可以试试。实质上的释放空间是用【`vector<类型>().swap(要释放空间的vector变量)`】，扩充空间用【`变量.resize(扩充到多大空间,填充内容)`】。我的程序最慢点耗时187ms，最大空间消耗为1.27MB。
```cpp
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> G[5005];
struct F
{
long long y, n;
};
vector<F> f[5005];
int c[5005],`d[5005], si[5005], n, q, tot;
inline void add(int a, int b)
{
G[a].push_back(b);
}
void dfs(int x)
{
int s = G[x].size(), e;
long long rr, ss, tt;
si[x] = 1;
//f[x].insert(f[x].begin(), n+1, (F){998244353998244353, 998244353998244353});
f[x].resize(2);
f[x][0].n = 0;///什么都不用
f[x][0].y = 998244353998244353;
f[x][1].y = c[x] - d[x];
f[x][1].n = c[x];
///没有使用优惠券
///使用了优惠券
for(register int i = 0; i < s; i += 1)
{
e = G[x][i];
dfs(e);
f[x].resize(si[x]+si[e]+1, (F){998244353998244353, 998244353998244353});
for(register int j = si[x]; j >= 0; j -= 1)
for(register int k = 0; k <= si[e]; k += 1)
{
rr = f[x][j].n+f[e][k].n;
ss = f[x][j]`y+f[e][k].n;
tt = f[x][j].y+f[e][k].y;
if(rr <= tot && f[x][j+k].n > rr)
f[x][j+k].n = rr;
if(ss <= tot && f[x][j+k].y > ss)
f[x][j+k].y = ss;
if(tt <= tot && f[x][j+k].y > tt)
f[x][j+k].y = tt;
}
vector<F>().swap(f[e]);
si[x] += si[e];
}
//if(!s)
// f[x].resize(f[x].begin()+2, n-1, (F){998244353998244353, 998244353998244353});
}
int main()
{
scanf("%d%d", &n, &tot);
scanf("%d%d", &c[1], &d[1]);
for(register int i = 2; i <= n; i += 1)
{
scanf("%d%d%d`", &c[i], &d[i], &q);
add(q, i);
}
dfs(1);
for(register int i = n; i; i -= 1)
{
printf("%lld %lld\n", f[1][i].y, f[1][i].n);
if(f[1][i].y <= tot || f[1][i].n <= tot)
{
printf("%d", i);
return 0;
}
}
printf("0`");//might wrong at here
return 0;
}
```
-
-
-
抄题解的你绝对过不了。