303 条题解
-
-1
吴哥的女朋友 LV 8 @ 2018-10-16 16:35:30
#include <iostream> #include <algorithm> #include <cstring> using namespace std; int height[101], maxlenzheng[101], maxlenfan[101], maxlen[101]; int n; int main() { int i, j; cin >> n; for (i = 1; i <= n; i++) { cin >> height[i]; maxlenzheng[i] = 1; maxlenfan[i] = 1; } for (i = 2; i <= n; i++) for (j = 1; j < i; j++) if (height[i] > height[j]) maxlenzheng[i] = max(maxlenzheng[i], maxlenzheng[j] + 1); for (i = n - 1; i >= 1; i--) for (j = n; j > i; j--) if (height[i] > height[j]) maxlenfan[i] = max(maxlenfan[i], maxlenfan[j] + 1); for (i = 1; i <= n; i++) maxlen[i] = maxlenzheng[i] + maxlenfan[i] - 1; cout << n - *max_element(maxlen + 1, maxlen + 1 + n) << endl; system("pause"); return 0; } -
-1
int a[N],b[N],g[N],l[N],r[N];
int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) b[i]=a[n-i+1]; memset(g,63,sizeof(g)); for(int i=1;i<=n;i++){ int k=lower_bound(g+1,g+n+1,a[i])-(g+1); l[i]=k+1; g[k+1]=a[i]; } memset(g,63,sizeof(g)); for(int i=1;i<=n;i++){ int k=lower_bound(g+1,g+n+1,b[i])-(g+1); r[i]=k+1; g[k+1]=b[i]; } int maxv=0; for(int i=1;i<=n;i++){ maxv=max(maxv,l[i]+r[n-i+1]); } cout<<n-maxv+1; return 0; } -
-1
#include <cstdio>
int main(){
int n,a[110],f1[110]={0},f2[110]={0};
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]<a[i]&&f1[i]<f1[j]+1)
f1[i]=f1[j]+1;
for(int i=n-1;i>=1;i--)
for(int j=n;j>i;j--)
if(a[j]<a[i]&&f2[i]<f2[j]+1)
f2[i]=f2[j]+1;
int ans=0;
for(int i=1;i<=n;i++)
if(f1[i]+f2[i]>ans)
ans=f1[i]+f2[i];
printf("%d",n-(ans+1));
return 0;
} -
-1
原来是输出出队人数
#include<iostream>
#include<cstdio>
using namespace std;
int n,ans=0,f[110],g[110],T[110];
int main(){
//freopen("in.txt","r",stdin);
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&T[i]);
for(i=1;i<=n;i++){
g[i]=1;f[i]=1;
}
for(i=1;i<=n;i++){
for(j=1;j<i;j++){
if(T[i]>T[j]){
f[i]=max(f[i],f[j]+1);
}
}
} //正着求最长非降子序列
for(i=n;i>=1;i--){
for(j=n;j>i;j--){
if(T[i]>T[j]){
g[i]=max(g[i],g[j]+1);
}
}
} ////反着求最长非增子序列
for(i=1;i<=n;i++){
ans=max(f[i]+g[i]-1,ans);
}
printf("%d",n-ans);
return 0;
}
-
-1
#include<bits/stdc++.h> using namespace std; int n,m,i,j,a[2000],b[2000],c[2000]; int main() { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=1,c[i]=1; for(i=1;i<=n;i++) for(j=1;j<i;j++) if(a[j]<a[i]) b[i]=max(b[i],b[j]+1); for(i=n;i>=1;i--) for(j=n;j>i;j--) if(a[j]<a[i]) c[i]=max(c[i],c[j]+1); for(i=1;i<=n;i++) m=max(m,b[i]+c[i]-1); printf("%d",n-m); return 0; } -
-1
正着一遍最长上升子序列 反着一遍
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1004;
int a[N],f[N],g[N];
int find(int n)
{
int ans=0;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]<a[i]&&f[j]+1>f[i])
f[i]=f[j]+1;
for(int i=n-1;i>=1;i--)
for(int j=i+1;j<=n;j++)
if(a[j]<a[i]&&g[j]+1>g[i])
g[i]=g[j]+1;
for(int i=1;i<=n;i++)
ans=max(ans,g[i]+f[i]-1);
return ans;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
fill(f,f+N,1);
fill(g,g+N,1);
cout<<n-find(n)<<endl;
return 0;
}
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms汗,交了两次.第一次写成两个不下降序列DP了......最恶心的是,测试数据居然可以通过,结果才20.
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
晕..竟然提交了2次才AC掉.郁闷~~~ -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms最长单调递增子序列与最长单调递减子序列的混合
最基础的动态规划 -
-1
EagleFantasy LV 3 @ 2007-11-10 18:52:37
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
1遍AC!
不过还是有很多地方要注意，个个变量的循环范围，初始值，都需要特别注意。 -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms这道题似乎只能先顺推,再倒推
我先顺推找到最大后再从最大往后找都错了 - -!
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms郁闷 ～～～～好长时间才AC啊 ， 纪念 纪念！！
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms太值得纪念了
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
终于过了^_^
正向DP高到低（右上左下）
反向DP高到低（左上右下）
结果是N-max{f[k]+g[k]|K∈[0..n-1]}+1
吴哥的女朋友
LV 8
@ 2018-10-16 16:35:30
