首页 > 其他 > 详细

P1311 选择客栈

时间:2019-10-09 23:37:38      阅读:80      评论:0      收藏:0      [点我收藏+]

嗯这道题我的做法是典型的用空间换时间

用a[i][j]记录颜色为i的客栈出现的坐标,每次枚举当前客栈到前一个同颜色的客栈间是否有符合条件的客栈,如果有,就是当前客栈之前出现的所有同色客栈数量,如果没有,就是上一个同色客栈的答案数,最后从头到尾遍历一遍每个客栈的答案累加,输出,结束

但是就在我写这篇博客的时候,我突然意识到,对于a数组,当当前节点为j时,我最多只用到了同色的客栈数以及a[i][j-1],那不就可以优化一维只记录上次同色客栈的答案数么???????那不就不用用空间换时间了?????

md我真是个智障。。

附上我无脑开的不知道浪费了多少空间的代码。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<stack>
 7 #include<deque>
 8 #include<algorithm>
 9 #define ll long long
10 using namespace std;
11 const ll oo=0x3f3f3f3f;
12 const ll N=200005;
13 const ll M=55;
14 
15 ll n,k,p,sum;
16 ll ans[N],a[M][N],b[N];
17 
18 ll Min(ll a,ll b){return a<b?a:b;}
19 ll Max(ll a,ll b){return a>b?a:b;}
20 ll Abs(ll a){return a>0?a:-a;}
21 
22 ll get(){
23     char zy=getchar();
24     ll z=1,y=0;
25     while(zy>9||zy<0){
26         if(zy==-) z=-1;
27         zy=getchar();
28     }
29     while(zy>=0&&zy<=9){
30         y=(y<<1)+(y<<3)+zy-0;
31         zy=getchar();
32     }
33     return z*y;
34 }
35 
36 int main(){
37     //freopen("P1311选择客栈.in","r",stdin);
38     //freopen("P1311选择客栈.out","w",stdout);
39     n=get();k=get();p=get();
40     for(ll i=1;i<=n;i++){
41         bool ok=false;
42         ll c=get();b[i]=get();
43         if(a[c][0]){
44             for(ll j=a[c][a[c][0]];j<=i;j++){
45                 if(b[j]<=p){
46                     ok=true;
47                     break;
48                 }
49             }
50             if(ok) ans[i]=a[c][0];
51             else ans[i]=ans[a[c][a[c][0]]];
52         }
53         a[c][++a[c][0]]=i;
54     }
55     for(ll i=1;i<=n;i++) sum+=ans[i];
56     printf("%lld\n",sum);
57     return 0;
58 }

 

P1311 选择客栈

原文:https://www.cnblogs.com/hahaha2124652975/p/11644870.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!