随机数
引领天下
2017-12-17 12:06:25
C++随机数
是一个神奇的算法。
比如说，可以用来AC动态规划。
例：
装箱问题：
```cpp
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int ans,n,c[105],w[105],v,s;
int main (){
scanf ("%d%d",&v,&n);
for (int i=1;i<=n;i++)scanf ("%d",&c[i]);
for (int i=1;i<=100000;i++){
s=0;
for (int j=1;j<=n;j++)if (s+c[j]<=v)s+=c[j]*(rand()%2);
ans=max(ans,s);
}
printf ("%d",v-ans);
return 0;
}
```
直接随机每个物品装不装，就AC了。。。
强大啊……~~（可能是因为卡到了某个数据的哈希？）~~
然后。。。
[~~稍微靠谱一点的随机数算法是这样的:~~](https://www.luogu.org/problemnew/show/P4703)