HDOJ 5000 Clone

HDOJ 5000 Clone

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

  所有的属性,以满足一定的条件,是,财产和等于sum/2结果最大.

Clone

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 574    Accepted Submission(s): 277




Problem Description
After eating food from Chernobyl, DRD got a super power: he could clone himself right now! He used this power for several times. He found out that this power was not as perfect as he wanted. For example, some of the cloned objects were tall, while some were short; some of them were fat, and some were thin. 

More evidence showed that for two clones A and B, if A was no worse than B in all fields, then B could not survive. More specifically, DRD used a vector v to represent each of his clones. The vector v has n dimensions, representing a clone having N abilities. For the i-th dimension, v[i] is an integer between 0 and T[i], where 0 is the worst and T[i] is the best. For two clones A and B, whose corresponding vectors were p and q, if for 1 <= i <= N, p[i] >= q[i], then B could not survive. 

Now, as DRD’s friend, ATM wants to know how many clones can survive at most.

 


Input
The first line contains an integer T, denoting the number of the test cases.

For each test case: The first line contains 1 integer N, 1 <= N <= 2000. The second line contains N integers indicating T[1], T[2], …, T[N]. It guarantees that the sum of T[i] in each test case is no more than 2000 and 1 <= T[i]. 

 


Output
For each test case, output an integer representing the answer MOD 10^9 + 7.
 


Sample Input
   
   
2 1 5 2 8 6

 


Sample Output
   
   
1 7

 


Source

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;

const LL mod=(1e9+7);

int v[2020],n;
LL sum,dp[2][2000400];

int main()
{
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%d",&n);
        sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",v+i);
            sum+=v[i];
        }
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            if(i==0)
            {
                for(int j=0;j<=v[i];j++) dp[0][j]=1;
                continue;
            }
            for(int j=0;j<=sum/2;j++)
            {
                int temp=0;
                for(int k=0;k<=v[i]&&k<=j;k++)
                {
                    temp=(temp+dp[(i%2)^1][j-k])%mod;
                }
                dp[i%2][j]=temp;
            }
        }
        printf("%d\n",dp[(n-1)%2][sum/2]);
    }
    return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117495.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 黑马程序员—wpf学习笔记四—banding的那些事

    黑马程序员—wpf学习笔记四—banding的那些事——-WindowsPhone7手机开发、.Net培训、期待与您交流!——-一、WPF中,对控件做数据banding,可以方便的进行赋值和获得值的操作:例如一:<Grid><SliderName=”Slider1″HorizontalAlignment=”Left”Margi…

    2022年10月13日
  • datagrip2020激活码mac_通用破解码

    datagrip2020激活码mac_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 旅游管理系统

    旅游管理系统旅游管理系统介绍要求:ER图代码介绍高级数据库布置的实验作业要求:题目:设计与实现一个旅游预订系统,该系统涉及的基本信息有航班,出租车,宾馆和客户等数据信息。实体和其特征属性举例如下:FLIGHTS(StringflightNum,intprice,intnumSeats,intnumAvail,StringFromCity,StringArivCity);H…

  • dropdown list_css中display中flex

    dropdown list_css中display中flexサンプル画面–>http://ns.adobe.com/mxml/2009″    xmlns:s=”library://ns.adobe.com/flex/spark”    xmlns:mx=”library://ns.adobe.com/flex/mx”    minWidth=”800″    minHeight=”400″>      import

    2022年10月10日
  • bm3d matlab,Note — BM3D「建议收藏」

    bm3d matlab,Note — BM3D「建议收藏」一、引言二、理论三、算法一、引言前面一篇说到Non-localmethod[1],可以归类到spatialmethod中,另外用的比较多的还有transformmethod,基于transformmethod的方法在imagedenoise中也取得了很好的效果,不过理论阐述会比较繁琐,如BLS-GSM-Wavelet。NLM去噪算法使用的是inter-patchcorrelation,而Wavel…

  • 使用navicat创建Oracle数据库[通俗易懂]

    使用navicat创建Oracle数据库[通俗易懂]navicat11.0.7Oracle11.20.第一次登陆,同plsql,用管理员登陆图0.1图0.2注意,这里需要是sysdba1.navicat连接数据库(本地的或者服务器上的都一样,本次截图演示的为本地数据库)navicat连接Oracle可能会有报错情况,另一篇里面写了这么配置连接成功后,打开图1:2.其他——目录——创建…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号