首页 > 代码库 > Hdu5000
Hdu5000
这题是网络赛的一个题.基本上属于猜想性的题目.很多东西不能深究,得猜,而猜也是有技巧的,可以暴力打表.
题意:clones有一些属性,每一个属性都是0-w[i]的任意一个值.每个clone都得有每个属性各一个属性值.如果制造出一堆这样的clones,他们之间不能存在一个clone的各方面属性都不小于另一个clone,求满足条件的最多clones数量.
思路:
dilworth定理和这个有点关系,但是好像没办法解这个题.也就是求一个反链使得里面包含的所有个体都不可比,即求最长反链,那么应该等于最少链覆盖数.然后就没有然后了...
猜想一,满足最多数量clones数的时候必然这些所有clone的属性之和都相等,等于一个定值.然而这题结果太大了,需要取模,所以如果dp求出所有属性之和,然后比较是不对的,取模..所以仅仅是这个猜想还是不够的.
猜想二,这个定值等于所有属性最大值之和除以2.这个能想到的大部分可能是因为题目描述中弱弱的说了一句 "It guarantees that the sum of T[i] in each test case is no more than 2000 and 1 <= T[i]. " 所有属性和不超过2000,如果和这个东西没关系说它干嘛.所以..
有了这两个猜想,写一个dp类似于背包就可以了.
后来到网上看了看,有人说了一个挺有道理的支持猜想二的说法.
如果有一个骰子,然你抛两次,两次得到的数字之和概率最大的是多少.就是说两次数字的和是哪一个数的时候概率最大.想想好像是7,为什么呢,因为无论第一次是哪一个数,第二次总有一个数可能和它的和是7,怎么求出来的呢.7=(6+6)/2+1,那么上题按照这个思路应该是sum/2+1才对,这不错了么?注意骰子上没有0!!而上题是从0开始的.具体原因我再想想.
AC代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <math.h> 5 #include <algorithm> 6 #include <stdlib.h> 7 using namespace std; 8 #define maxn 2005 9 #define MOD 100000000710 int f[maxn][maxn],t[maxn];11 int main()12 {13 int T,n,i,j,k,m;14 scanf("%d",&T);15 while(T--)16 {17 m=0;18 scanf("%d",&n);19 for(i=1;i<=n;i++)20 {21 scanf("%d",&t[i]);22 m+=t[i];23 }24 m/=2;25 memset(f,0,sizeof(f));26 for(i=0;i<=t[1];i++)27 f[1][i]=1;28 for(i=2;i<=n;i++)29 for(j=0;j<=m;j++)30 {31 for(k=0;k<=t[i];k++)32 if(j>=k)33 f[i][j]=(f[i][j]+f[i-1][j-k])%MOD;34 }35 cout<<f[n][m]<<endl;36 }37 return 0;38 }
Hdu5000