【Coci2009】podjela

Source and Judge

Coci2009
bzoj3090

Record

1h

Analysis

请先思考后再展开

因为不用求方案,不用考虑次序什么的,允许负数
显然次数不会比点数多,因为每条边单向
值很大而次数少,所以应该对次数背包而不是对值
$$
\begin{aligned}
& 设f(x,now)=maxup\\
& 1. f(y,b)<ned\\
& f_1(x,a+b+1)=f_0(x,a)-(ned-f(y,b))\\
& 2. f(y,b) \geq ned\\
& f_1(x,a+b)=f_0(x,a)\\
& f_1(x,a+b+1)=f_0(x,a)+f(y,b)-ned
\end{aligned}
$$
复杂度显然 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
const int MAX_N=2100;
int hou[MAX_N],siz[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int f[2][MAX_N][MAX_N],ned[MAX_N];
void chmax(int &x,int y) {x=max(x,y);}
void dp(int x,int fa)
{
int now=0;siz[x]=1;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dp(y,x);
for(int a=0;a<=siz[x];a++)
for(int b=0;b<=siz[y];b++)
{
int up=f[0][y][b];if(up==f[0][0][0]) continue;
chmax(f[now^1][x][a+b+1],f[now][x][a]+up-ned[y]);
if(up>=ned[y]) chmax(f[now^1][x][a+b],f[now][x][a]);
}
siz[x]+=siz[y];
memset(f[now][x],-63,sizeof f[now][x]);now^=1;
}
memcpy(f[0][x],f[now][x],sizeof f[0][x]);
}
void main()
{
memset(f,-63,sizeof f);
int n,st;scanf("%d%d",&n,&st);
for(int i=1;i<=n;i++) f[0][i][0]=st,scanf("%d",&ned[i]);
for(int i=1;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
dp(1,0);
int ans=-1;for(int i=n;i>=0;i--) if(f[0][1][i]>=ned[1]) ans=i;
printf("%d",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8a58.html
转载请注明出处,谢谢!