首页 > 代码库 > hdu 5064 Find Sequence

hdu 5064 Find Sequence

2024-07-27 19:15:25   220人阅读

 

Find Sequence

Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 279    Accepted Submission(s): 80


Problem Description
Give you an positive integer sequence a1,a2,…,ai,…,an, and they satisfy a1+a2+…+ai+…+an=M(0<M≤222).
We can find new sequence b1=aid1,b2=aid2,…,bx=aidx,…,by=aidy,…,bt=aidt, where if x != y then idx!=idy. and this sequence satisfy:
(1) b1≤b2≤…≤bt 
(2) b2−b1≤b3−b2≤?≤bt−bt−1
We can find many sequences b1,b2,b3,…,bt. But we only want to know maximum t.
 

 

Input
The first line in the input file is an Integer T(1≤T≤30).
The first line of each test case contains two integer n,M(0<M≤222).
Then a line have n integer, they represent a1,a2,…,ai,…,an.
 

 

Output
For each test case, output the maximum t.
 

 

Sample Input
26 193 2 1 3 4 61 41943044194304
 

 

Sample Output
51
Hint
For the first testcase, The Sequence is 1 2 3 4 6
 

 

Source
BestCoder Round #13
 
题意: 在一个数列里面取出一些数，满足一些条件
官方题解
首先考虑解的结构一定是C1,C1,…,C1,C2,C3,…,Cm这种形式，其中满足C1<C2<C3<…<Cm所以对a1,a2,a3,…,an去重后从小到大排序得到c1,c2,c3,…,cx其中x是sqrt(M)级别的，用DP[i][j]表示以ci和cj结尾的满足条件的最长序列首先初值化 DP[i][i]=count(ci) 即ci在原序列中的个数。而dp[i][j]=max(dp[k][i] 其中k≤i还满足ci−ck≤cj−ci)+1这样的复杂度是 O(x^3),在题中x最大为1000级别所以会超时，要使用下面优化因为 dp[i][j]=max(dp[k][i] 其中k≤i还满足ci−ck≤cj−ci)+1dp[i][j+1]=max(dp[k][i] 其中k≤i还满足ci−ck≤cj+1−ci)+1注意到cj+1>cj 所以满足ci−ck≤cj−ci的dp[k][i]必然满足ci−ck≤cj+1−ci因而不必重复计算即最后复杂度可以为O(x^2).
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define maxn (1<<22)+10using namespace std;int cnt[maxn],c[2010],dp[2010][2010];int main(){    int i,n,m,j,k;    int tmp,T,x,ans;    cin >>T ;    while(T--)    {        scanf("%d%d",&n,&m) ;        memset(cnt,0,sizeof(cnt));        for( i = 1 ; i <= n ;i++)        {            scanf("%d",&x) ;            cnt[x]++;        }        n = 0 ;        memset(dp,0,sizeof(dp));        ans=0;        for( i =0 ; i <= m ;i++)if(cnt[i])        {            c[++n]=i;            dp[n][n]=cnt[i];            ans=max(cnt[i],ans);        }        for( i = 1 ; i <= n ;i++)        {            tmp=dp[i][i];            k = i ;            for( j = i+1 ; j <= n ;j++)            {                for( ; k >= 1 ;k--)                {                    if(c[j]-c[i] >= c[i]-c[k])                        tmp = max(tmp,dp[k][i]+1) ;                    else break ;                }                dp[i][j]=tmp;                ans=max(ans,dp[i][j]);            }        }        printf("%d\n",ans);    }    return 0 ;}
View Code

 



hdu 5064 Find Sequence


联系
我们