yltx's blog

yltx's blog

Κοιτάζοντας πάνω στον έναστρο ουρανό, κάτω στη γη.

随机数

posted on 2017-12-17 12:06:25 | under 玄学 |

C++随机数

是一个神奇的算法。

比如说,可以用来AC动态规划。

例:

装箱问题:

#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了。。。

强大啊……(可能是因为卡到了某个数据的哈希?)

然后。。。

稍微靠谱一点的随机数算法是这样的: