2019 计蒜之道初赛第三场 A题淘宝商品价格大PK

69 阅读 0 评论 46 点赞

我是靠谱客的博主哭泣外套，这篇文章主要介绍2019 计蒜之道初赛第三场 A题淘宝商品价格大PK，现在分享给大家，希望可以做个参考。

原题地址
这道题题意就是找最长上升子序列长度在随机删除一个数后，输出最长上升子序列长度减少的数量。
大佬们说是很简单，但身为菜鸟的我，在比赛的时候连题目想要输出啥，都没明白。。。所以理所当然的WA了好多发之后放弃这道题，在比赛结束之后，问了一下大佬，然后大佬告诉我用最长上升子序列的板子就行。至于最长上升子序列是什么，请诸位移步这里。
附上刚刚明白如何做这道题的我的代码：

复制代码

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
int dp[110],a[110];
int b[110];
int f(int x)
{
int len = 1,l,r,mid;
dp[1] = a[1];
for(int i=2;i<=x;i++)
{
l = 1;
r = len;
while(l <= r){
mid = (l+r)/2;
if(a[i] > dp[mid])
l = mid + 1;
else
r = mid - 1;
}
dp[l] = a[i];
if(l > len)
len = l;
}
return len;
}
int f2(int x)
{
int len = 1,l,r,mid;
dp[1] = b[1];
for(int i=2;i<=x;i++)
{
l = 1;
r = len;
while(l <= r){
mid = (l+r)/2;
if(b[i] > dp[mid])
l = mid + 1;
else
r = mid - 1;
}
dp[l] = b[i];
if(l > len)
len = l;
}
return len;
}
int main()
{
int n,ans,ans2,cnt = 0 ;
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>a[i];
}
ans = f(n);
for(int i=1;i<=n;i++)
{
int k = 0;
ans2 = 0;
memset(dp,0,sizeof(dp));
for(int j=1;j<=n;j++)
{
if(j != i){
b[++k] = a[j];
}
}
ans2 = f2(n-1);
if(ans2 != ans){
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}