「NOIP模拟赛」Incr
「题目描述」
数列 A1,A2,…,AN，修改最少的数字，使得数列严格单调递增。
「输入格式」
第 1 行，1 个整数 N
第 2 行，N 个整数 A1,A2,…,AN
「输出格式」
1 个整数，表示最少修改的数字
「样例输入」
3
1 3 2
「样例输出」
1
「数据范围」
对于 50% 的数据，N ≤ 10^3
对于 100% 的数据，1 ≤ N ≤ 10^5,1 ≤ Ai ≤ 10^9
题解
暴力可以用f[i][j]表示前i个最后一个改为j的方案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans=inf,n; int a[1005],f[1005][1005]; int main() { memset(f,127,sizeof(f)); n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=0;i<=1000;i++) if(i==a[1])f[1][i]=0; else f[1][i]=1; for(int i=2;i<=n;i++) for(int x=0;x<=1000;x++) { for(int y=0;y<x;y++) f[i][x]=min(f[i][x],f[i-1][y]); if(x!=a[i])f[i][x]++; if(i==n)ans=min(ans,f[i][x]); } printf("%d\n",ans); return 0; } |
ai减去下标求最长上升子序列ans。。。答案是n-ans
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,top,ans; int a[100005],best[100005]; int find(int x) { int l=0,r=ans,t=0; while(l<=r) { int mid=(l+r)>>1; if(x>=best[mid])t=mid,l=mid+1; else r=mid-1; } return t; } void solve() { for(int i=0;i<=n;i++)best[i]=inf; best[0]=-inf; for(int i=1;i<=n;i++) { int t=find(a[i]); best[t+1]=min(best[t+1],a[i]); ans=max(ans,t+1); } } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)a[i]-=i; solve(); printf("%d\n",n-ans); return 0; } |
Subscribe
计数器 9315294
OI 课件=>
OI 课件=>