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

本文主要是介绍Codeforces Round #323 (Div. 1) B. Once Again...，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

#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;
}

这篇关于Codeforces Round #323 (Div. 1) B. Once Again...的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---