hdu-5568SUM (dp)

sequence2

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

Problem Description

Given an integer array bi with a length of n, please tell me how many exactly different increasing subsequences.

P.S. A subsequence bai(1≤i≤k) is an increasing subsequence of sequence bi(1≤i≤n) if and only if 1≤a1<a2<...<ak≤n and ba1<ba2<...<bak.
Two sequences ai and bi is exactly different if and only if there exist at least one i and ai≠bi.

 

Input

Several test cases(about 5)

For each cases, first come 2 integers, n,k(1≤n≤100,1≤k≤n)

Then follows n integers ai(0≤ai≤109)

 

Output

For each cases, please output an integer in a line as the answer.

 

Sample Input

3 2 1 2 2 3 2 1 2 3

 

Sample Output

2 3

 

Source

BestCoder Round #63 (div.2)

 

Recommend

hujie

 

Statistic | Submit | Discuss | Note

令{A}_{i}=f({A}_{i})-{A}_{i}A​i​​=f(A​i​​)−A​i​​,然后求一遍最大连续子序列和就能知道最多能增加的值。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<cstdio>
#include<string.h>
typedef long long ll;
using namespace std;
ll a[100005];
ll b[100005];

int main(void)
{
    ll n,i,j,k,p,q;

    while(scanf("%lld",&n)!=EOF)
    { ll tt=0;
        for(i=0; i<n; i++)
        {
            scanf("%lld",&a[i]);
            tt+=a[i];
        }
        for(i=0; i<n; i++)
        {
            b[i]=(1890*a[i]+143)%10007-a[i];
        }
        ll sum=0;
        ll cnt=b[0];
        if(sum<cnt)
        {
            sum=cnt;
        }
        for(i=1; i<n; i++)
        {
            if(b[i-1]>=0)
            {
                b[i]+=b[i-1];

            }
            if(sum<b[i])
            {
                sum=b[i];
            }
        }
        if(sum<0)
        {
            sum=0;
        }
        printf("%d
",sum+tt);
    }
    return 0;


}