Luogu P352 没有上司的舞会
题意即无相邻两点的点集的和的最大值
正解
显然是个树形DP,f[i] [0/1]表示在i节点及其子树上不选i/选i的最大和
但是正解没意思
乱搞
思路
讲讲乱搞的做法:
显然的,有一种贪心方法是“能取则取”, 然而非常好卡
在此基础上我们进行瞎整优化
对于每一个可以选取的点,有概率地选取与不选取
这样每次的复杂度为O(N),做10000~20000次,在概率学上达到理论的正解
其实达不到
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int used[100001], n;
int head[100001], nxt[100001], to[100001], v[100001], tot;
int a[100001], ans;
void add(int x, int y)
{
nxt[++tot] = head[x];
head[x] = tot;
to[tot] = y;
return;
}
void gao(int x, int q, int from)
{
if(q)
{
if(rand() % 1000)
{
ans += a[x];
for(int i = head[x]; i; i = nxt[i])
{
int y = to[i];
if(y != from)
{
gao(y, 0, x);
}
}
return;
}
}
for(int i = head[x]; i; i = nxt[i])
{
int y = to[i];
if(y != from)
{
gao(y, 1, x);
}
}
return;
}
int luangao(int seed)
{
ans = 0;
srand(408020617 * seed % 1002051284);
rand();
int xxx = rand() % n + 1;
gao(xxx, rand() % 1000, xxx);
return ans;
}
signed main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{scanf("%lld", &a[i]);if(a[i] < 0) a[i] = 0;}
for(int i = 1; i < n; i++)
{
int x, y;
scanf("%lld%lld", &x, &y);
add(x, y);
add(y, x);
}
int aannss = -2147483647;
int yyy = n == 6000 ? 10000 : 20000;
for(int i = 1; i <= yyy; i++)
aannss = max(aannss, luangao(i));
cout << aannss << endl;
return 0;
}
概率的话,经测试1/1000不选分较高比较合适
细节
1.随机选取root枚举分更多更具普遍性
2.更改(瞎输入)随机数种子,拒绝伪随机
3.依据n范围确定循环次数防止TLE
4.若a[i] < 0则将它变成0,保证随机化最优
5-1.10年OI一场空,不开long long见祖宗
5-2.#define int long long 是个好东西
5-3.int main()怎么办?signed表示整型!
5-4.虽然这题并不用开long long
//附调代码的提交记录