Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)-C. The Phone Number-白红宇

Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)-C. The Phone Number

阅读量：4114 次

发布时间：2019-05-25

本文共 665 字，大约阅读时间需要 2 分钟。

C. The Phone Number

题意：给你n个数字从1到n，现在让你用这n个数字构造一个序列，使得最长上升子序列和最长下降子序列的和最小。

思路：我们可以先打一个表观察一下规律，通过打标找规律我们可以发现，对于n<=x*y，当x+y最小的时候就是最小的和，通过分析我们可以发现，我们相当于是把n个数字分成x组，使得每组最多y个数字，在每一组中构成的是最长下降序列，x组构成的是最长上升子序列。打表我是把n的全排列构造出来，然后求每个全排列的最长上升子序列和最长下降子序列的和，把和最小的序列打印出来。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           using namespace std;int main(){ int n; scanf("%d",&n); if(n==1) { cout<<1<
           
            =n) { minn=x+y+1; a=x+1; b=y; } if(x+y+1
            
             =n) { minn=x+y+1; a=x; b=y+1; } } } int f=0; int t=0; for(int i=1; i+b-1<=n; i+=b) { int x=i+b-1; for(int j=x; j>=i; j--) { if(f==0) { cout<
             
              t; j--) { if(f==0) { cout<

转载地址：http://obgsi.baihongyu.com/

你可能感兴趣的文章