Hdu5000

柔情只为你懂 2021-12-10 06:41 97阅读 0赞

[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代码:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 1000000007
    10 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 }

posted on 2014-10-08 21:59 [Lonely patients][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

转载于:https://www.cnblogs.com/Acmerfighting/p/4012149.html

[Hdu5000]: https://www.cnblogs.com/Acmerfighting/p/4012149.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/0a0661375dbc4df3a5a2a8cafe9f302d.png
[Lonely patients]: https://www.cnblogs.com/Acmerfighting/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=4012149