神奇的题目
想了3个做法
假·贪心、真·DP、真·贪心
全部交上去
分别获得40、90、100的好成绩
蚌埠住了
1.假·贪心
考虑从孩子节点开始一直到指定的根节点u
到中途某个节点，信号强度不够用了，那么对应根节点u的放大器数+1
这样贪心是不对的，只有WA40分
因为选择某些节点可能会对于之后的整棵子树减少不必要的消费
//...WA40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e4+10;
ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
ll head[N],to[N*2],tot=0,nxt[N*2],dis[N*2];
void add(ll u,ll v,ll w) {
nxt[++tot]=head[u];
to[tot]=v;
dis[tot]=w;
head[u]=tot;
}
ll n,k,oo,maxx=0,cnt=0;
void dfs(ll u,ll fa,ll energy) {
for(ll i=head[u];i;i=nxt[i]) {
ll v=to[i],w=dis[i];
if(v==fa) continue;
if(energy-w<=0) dfs(v,u,oo),cnt++;
else dfs(v,u,energy-w);
}
}
int main() {
n=read();
for(ll i=1;i<=n;i++) {
k=read();
for(ll j=1;j<=k;j++) {
ll u=read(),w=read();
add(i,u,w);
maxx=max(maxx,w);
}
}
oo=read();
if(maxx>=oo) printf("No solution.\n");
else {
dfs(1,1,oo);
printf("%lld\n",cnt);
}
return 0;
}
2.真·DP
那么考虑dp
dp[u][0/1] 表示遍历以u为根的子树所需要的放大器数量 0/1表示是否选择u
动态规划选择最优点
以此类推，最后答案汇总到根节点1上
然后你就有TLE90分的好成绩?
//...TLE90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e4+10;
ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
ll head[N],to[N*2],tot=0,nxt[N*2],dis[N*2];
void add(ll u,ll v,ll w) {
nxt[++tot]=head[u];
to[tot]=v;
dis[tot]=w;
head[u]=tot;
}
ll n,k,oo,maxx=0,cnt=0;
ll dp[N][2];
void dfs(ll u,ll fa,ll energy) {
dp[u][0]=0;
dp[u][1]=1;
for(ll i=head[u]; i; i=nxt[i]) {
ll v=to[i],w=dis[i];
if(v==fa) continue;
if(energy-w>0) {
dfs(v,u,energy-w);
dp[u][0]+=min(dp[v][0],dp[v][1]);
} else {
dp[u][0]=1e9+7;
}
dfs(v,u,oo-w);
dp[u][1]+=min(dp[v][0],dp[v][1]);
}
}
int main() {
n=read();
for(ll i=1; i<=n; i++) {
k=read();
for(ll j=1; j<=k; j++) {
ll u=read(),w=read();
add(i,u,w);
maxx=max(maxx,w);
}
}
oo=read();
if(maxx>=oo) printf("No solution.\n");
else {
dfs(1,0,oo);
printf("%lld\n",min(dp[1][0],dp[1][1]));
}
return 0;
}
3.真·贪心
然后你不得不考虑优化贪心算法
鉴于有时候在某个点父亲加放大器可能更优
从子节点开始，再跑贪心，该加的时候加就可以了
然后就100分了...
//...AC100
//开始一直以为TLE是long long或者手写前向星的问题
//后面改了一下，问题不大
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int N=2e4+10;
int read() {
int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct node{
int v,w;
};
vector<node> p[N];
int n,k,oo,maxx=0,ans=0;
int d[N],dfa[N];
void dfs(int u,int fa) {
for(int i=0; i<p[u].size(); i++) {
int v=p[u][i].v,w=p[u][i].w;
if(v==fa) continue;
dfa[v]=w;
dfs(v,u);
d[u]=max(d[u],d[v]+w);
}
if(d[u]+dfa[u]>oo) ans++,d[u]=0;
}
int main() {
n=read();
for(int i=1; i<=n; i++) {
k=read();
for(int j=1; j<=k; j++) {
int u=read(),w=read();
p[i].push_back( {u,w} );
maxx=max(maxx,w);
}
}
oo=read();
if(maxx>=oo) printf("No solution.\n");
else {
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}