tyvj1166

• 背景

  • 众所周知，企鹅帮中的Kowalski在这个帮派中起到了智囊的作用，关键时刻总能帮助老大Skipper解决一些困难的问题（虽然有时也会出些馊主意，且过分依赖科学和数据）。
    Kowalski也经常玩他的算盘！！！（他对算盘的迷恋程度相当于Rico对刀的迷恋程度！！！）不过，他可不是像一些弱智儿童一样算一些1+1=2，1+2=3，2+2=？的问题（。。。），而是经常“遨游在神秘的科学世界里探索新的发现”，这不，今天他又发现了一个东西：由于是他的发明，所以他暂且将该项发现的专利名称定为：科沃斯基数。。。
    科沃斯基数是这样的啊：首先呢，会给你N个数，然后呢，需要你求出，这N个数里，最多能找到多少个数，能构成严格的递减序列（可以不相邻哦！！！），然后将最多个数赋为K，然后呢，再输入一个2000位以内的数L，将L和K相加得到一个高精度数，将这个高精度数去掉指定的O位以后最大与最小的两种情况分别输在在两行。
    Kowalski想让你编个程序，算出这最大和最小的两个数！！！别忘了，事成之后，Kowalski会给你10000000000000000000000000000000000000000000000000 mod 10-100000元。。。

• 输入格式

  • 第一行一个整数N，表示有N个数；
    第二行N个正整数，表示这N个数；
    第三行一个高精度数L；
    第四行一个数O；

• 输出格式

  • 两行。
    第一行为K+L这个高精度数去掉O位后尽可能大的数；
    第二行为K+L这个高精度数去掉O位后尽可能小的数；

• 输入

  • 2
    2 1
    9999999997
    5

• 输出

  • 99999
    99999

最长下降子序列+高精度加法+奇怪的贪心

贪心我看了题解，脑补了半天，大概是这样：
大的：从高位往低位，若num[i]<num[i+1]则去掉第I个。
小的：从高位往低位，若num[i]>num[i+1]则去掉第I个。
若不满足，则直接去掉个位（脑补123456789和987654321就明白了…）

厚颜无耻看题解代码还特别长的人的代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int size=10010;
struct bign{int len,num[size];bign(){len=1;memset(num,0,sizeof(num));}bign(int x){len=0;memset(num,0,sizeof(num));do{num[++len]=x%10;x/=10;}while(x);}   
};bign operator +(const bign &a,const bign &b)
{bign ans;int i=1,x=0;while(i<=a.len||i<=b.len){x=a.num[i]+b.num[i]+x;ans.num[i]=x%10;x/=10;i++;}ans.num[i]=x;while(i>1&&ans.num[i]==0) i--;ans.len=i;return ans;
}void scan(bign &a)
{string s;cin>>s;int l=a.len=s.length();for(int i=0;i<l;i++)a.num[l-i]=s[i]-'0'; 
}int num[size],dp[size];
int maxn[size],minn[size];void print(const bign &a)
{for(int i=a.len;i>=1;i--) printf("%d",a.num[i]); puts("");
}void opemax(int k,int len)
{while(k--){int pos=0;for(int i=1;i<len;i++) {if(maxn[i]<maxn[i+1]){pos=i;break;}}if(pos){for(int i=pos;i<len;i++) maxn[i]=maxn[i+1];}len--;}
}
void opemin(int k,int len)
{while(k--){int pos=0;for(int i=1;i<len;i++) {if(minn[i]>minn[i+1]){pos=i;break;}}if(pos){for(int i=pos;i<len;i++) minn[i]=minn[i+1];}len--;}
}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&num[i]);}int maxlen=0;for(int i=1;i<=n;i++){dp[i]=1;for(int j=1;j<i;j++){if(num[j]>num[i]) dp[i]=max(dp[j]+1,dp[i]);}maxlen=max(maxlen,dp[i]);}bign f; scan(f); f=f+maxlen;for(int i=f.len;i>=1;i--){maxn[f.len-i+1]=minn[f.len-i+1]=f.num[i];}int k;scanf("%d",&k);//  print(f);int len=f.len;opemax(k,len);opemin(k,len);for(int i=1,flag=1;i<=len-k;i++) {if(maxn[i]) flag=0;else if(flag) continue;printf("%d",maxn[i]);}puts("");for(int i=1,flag=1;i<=len-k;i++) {if(minn[i]) flag=0;else if(flag) continue; printf("%d",minn[i]);}return 0;
}
/*
2
2 1
987654319
3
*/