Description
Input
White spaces can occur freely in the input. The input data are correct and terminate with an end of file.
Output
For each set of data the program prints the result to the standard output from the beginning of a line.
Sample Input
6 5 2 1 4 5 3 3 1 1 1 4 4 3 2 1
Sample Output
3 1 1
Hint
Source
#include <iostream> const int N = 100000+100; using namespace std; int a[N], f[N], d[N]; //d[i]用于记录以i结尾的严格上升子序列最长长度; int bsearch(int f[], int size, int a) { int l=0, r= size-1; while(l <= r) { int mid=(l+r)>>1; if(a >f[mid-1] && a<= f[mid]) return mid; // a >=f[mid] && a< f[mid]; else if(a <f[mid]) r= mid-1; else l= mid+1; } } int LIS(int a[], int n) { int j, size= 1; f[0]= a[0]; d[0]= 1; for(int i=1; i< n; i++) { if(a[i] <= f[0]) j= 0; // < else if(a[i] >f[size-1]) j= size++; // >= else j =bsearch(f, size, a[i]); f[j]= a[i]; d[i]= j+1; } return size; } int main() { int n; while(scanf("%d", &n) != EOF) { for(int i=0; i< n; i++) scanf("%d", &a[i]); LIS(a, n); //int maxL= LIS(a, n); int maxL= 0; for(int i=0; i< n; i++) maxL=max(maxL, d[i]); printf("%d\n", maxL); } return 0; }
LIS变形 hdoj5256
序列变换
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
请输出最少需要修改多少个元素。
Input
T (1 \leq T \leq 10)，表示有多少组数据
每一组数据：
第一行输入一个N (1 \leq N \leq 10^5)，表示数列的长度
第二行输入N个数A_1, A_2, …, A_n。
每一个数列中的元素都是正整数而且不超过10^6。
Output
Case #i:
然后输出最少需要修改多少个元素。
Sample Input
Sample Output
#include <iostream> const int N = 100000+100; using namespace std; int a[N], f[N], d[N]; int bsearch(int f[], int size, int a) { int l=0, r= size-1; while(l <= r) { int mid=(l+r)>>1; if(a >= f[mid-1] && a< f[mid]) return mid; else if(a <f[mid]) r= mid-1; else l= mid+1; } } int LIS(int a[], int n) { int j, size= 1; f[0]= a[0]; d[0]= 1; for(int i=1; i< n; i++) { if(a[i] < f[0]) j= 0; else if(a[i] >= f[size-1]) j= size++; else j =bsearch(f, size, a[i]); f[j]= a[i]; d[i]= j+1; } return size; } int main() { int n, Q=1; int t; scanf("%d", &t); while( t--) {scanf("%d", &n); for(int i=0; i< n; i++) { scanf("%d", &a[i]); a[i]-= i; } LIS(a, n); int maxL= 0; for(int i=0; i< n; i++) maxL=max(maxL, d[i]); printf("Case #%d:\n%d\n", Q++, n- maxL); } return 0; }
3、
第十四个目标
Accept: 14 Submit: 26
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
目 暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算，柯南追踪伤害阿笠博士的凶手，根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经 过一系列的推理后，柯南发现受害者的名字均包含扑克牌的数值，且扑克牌的大小是严格递增的，此外遇害者与毛利小五郎有关。
为了避免下一个遇害者的出现，柯南将可能遭到暗算的人中的数字按关联程度排列了出来，即顺序不可改变。柯南需要知道共有多少种可能结果，满足受害人名字出现的数字严格递增，但是他柯南要找出关键的证据所在，所以这个任务就交给你了。
(如果你看不懂上面在说什么，这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。)
Input
多组数据(<=10)，处理到EOF。
第一行输入正整数N(N≤100 000)，表示共有N个人。
第二行共有N个整数Ai(1≤Ai≤10^9)，表示第i个人名字中的数字。
Output
每组数据输出一个整数，表示所有可能的结果。由于结果可能较大，对1 000 000 007取模后输出。
Sample Input
Sample Output
Source
福州大学第十三届程序设计竞赛
//树状数组+dp+离散化 ; #include<cstdio> #include <cstring> #include <algorithm> using namespace std; const int mx = 100005; const int mod = 1000000007; int tree[mx], a[mx], dis[mx], n; ///从右下往左上“看” bool cmp(int x, int y) { if (a[x] != a[y]) return a[x] < a[y]; return x > y; } void add(int pos, int x) { for (; pos <= n; pos += pos & -pos) tree[pos] = (tree[pos] + x) % mod; } int sum(int pos) { int res = 0; for (; pos; pos -= pos & -pos) res = (res + tree[pos]) % mod; return res; } int main() { while(scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), dis[i] = i; sort(dis + 1, dis + n + 1, cmp); memset(tree, 0, sizeof(tree)); for (int i = 1; i <= n; i++) add(dis[i], sum(dis[i]) + 1); printf("%d\n", sum(n)); } return 0; }
转载于:https://www.cnblogs.com/soTired/p/5438584.html
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/109051.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...