Codeforces Round #323 (Div. 1) B. Once Again...

怼烎@ 2022-08-09 02:11 18阅读 0赞

简单DP  
给了hint之后规律特别明显。  
我们可以明显发现，当n个数全部被选择完之后，就选择所有数里面最大的那个。  
那么最多选多少次能够将n个数选择完毕呢？  
样例是选了2次选择完的  
那么举一个例子5,4,3,2,1。这个就需要选择5次。因此最坏情况就是n次。  
如果T≤n→N=T×n，那么明显可以暴力直接做。  
否则，我们至多做n次选择，可以将所以的数选择完毕，也就是N=n2。  
复杂度刚好可以。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=105;
    int n,T;
    int a[maxn*maxn];
    int dp[maxn*maxn];
    int s[maxn*maxn];
    int p,v;
    int cnt[305];
    int main()
    {
    // freopen("input.txt","r",stdin);
        while(cin>>n>>T)
        {
            memset(cnt,0,sizeof(cnt));
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                cnt[a[i]]++;
            }
            for(int i=n+1;i<=min(T,n)*n;i++)a[i]=a[i-n];
            int top=0;
            int ans=0,anspos;
            for(int i=1;i<=min(T,n)*n;i++)
            {
                int L=1,R=top+1;
                while(L<R)
                {
                    int M=L+(R-L)/2;
                    if(a[i]>=s[M])L=M+1;
                    else R=M;
                }
                dp[i]=L;
                ans=max(ans,dp[i]);
                if(L>top)s[++top]=a[i];
                else s[L]=min(s[L],a[i]);
            }
            int Max=0;
            for(int i=1;i<=300;i++)Max=max(Max,cnt[i]);
            ans+=Max*max(T-n,0);
            cout<<ans<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #572 (Div. 2)B

B. Number Circle 题目链接：[http://codeforces.com/contest/1189/problem/B][http_codeforces.

小灰灰/ 2023年08月17日 15:40/ 0 赞/ 135 阅读

相关 Codeforces Round #570 (Div. 3)B

B - Equalize Prices 题目链接：[http://codeforces.com/contest/1183/problem/B][http_codeforc

谁践踏了优雅/ 2023年08月17日 15:40/ 0 赞/ 114 阅读

相关 Codeforces Round #323 (Div. 1) B. Once Again...

简单DP 给了hint之后规律特别明显。我们可以明显发现，当n个数全部被选择完之后，就选择所有数里面最大的那个。那么最多选多少次能够将n个数选择完毕呢？样

怼烎@/ 2022年08月09日 02:11/ 0 赞/ 19 阅读

相关 Codeforces Round #320 (Div. 1) B. "Or" Game

贪心思路：因为是或的关系，所以只要使得某个数尽可能得大就可以了。于是第一个想法是，选出最大的那个数，使得它乘以k次最大。但是这样会有部分情况是错误的。比如

小鱼儿/ 2022年08月08日 14:46/ 0 赞/ 144 阅读

相关 Codeforces Round #305 (Div. 1) A && B

547A - Mike and Frog 先考虑，从h1\->a1的过程，计算需要的时间如果在M次内，没有到达则不可到达然后再判断是否符合h2\->a2的时间

冷不防/ 2022年08月05日 00:55/ 0 赞/ 169 阅读

相关 Codeforces Round #565 (Div. 3) B

B. Merge it！题目链接：[http://codeforces.com/contest/1176/problem/B][http_codeforces.com_

谁借莪１个温暖的怀抱￠/ 2022年01月07日 15:35/ 0 赞/ 158 阅读

相关 Codeforces Round #569 (Div. 1)

[Codeforces Round \569 (Div. 1)][Codeforces Round _569 _Div. 1] A Valeriy and Deque

川长思鸟来/ 2021年12月24日 08:39/ 0 赞/ 203 阅读

相关 Codeforces Round #545 (Div. 1)

A - Skyscrapers 暴力离散化之后再乱搞一搞就好了。 include<bits/stdc++.h> define qmin(x,y) (x=min(

短命女/ 2021年12月24日 08:37/ 0 赞/ 191 阅读

相关 Codeforces Round #568 (Div. 2)B

B. Email from Polycarp 题目链接：[http://codeforces.com/contest/1185/problem/B][http_codef

Myth丶恋晨/ 2021年12月03日 22:43/ 0 赞/ 239 阅读

相关 Codeforces Round #564 (Div. 1)

A 太难了，一半时间刚这题还没做出来，简直自闭了。实际上分两种情况，一种很简单直接放，另一种就是要0,0,…,0,1,2,…,n，然后直接贪心，显然我是把情况判断错误一直没调

比眉伴天荒/ 2021年11月01日 08:46/ 0 赞/ 217 阅读