当前位置：首页 > news >正文

Day6下午题解1

news 来源：原创 2024/5/9 22:59:24

预计分数：100+?+30=130+?

实际分数：100+25+30=155

T1

https://www.luogu.org/problem/show?pid=T15920

DP裸题，用dp[i][0]表示到达i，第i个位置不选，dp[i][1]表示到达i，第i个选的最大值

对于每一个询问，只有最高位为1的时候是有限制的，我们用now维护

转移也比较好写

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #define LL long long 
 8 using namespace std;
 9 const LL MAXN=1e6+10;
10 const LL INF=0x7fffff;
11 inline LL read()
12 {
13     char c=getchar();LL flag=1,x=0;
14     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
15     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;
16 }
17 LL n,m;
18 char s[MAXN];
19 LL a[MAXN];
20 LL maxpos;//最高位的位置 
21 LL dp[MAXN][3];
22 bool flag=0;
23 LL fastpow(LL a,LL p)
24 {
25     LL base=1;
26     while(p)
27     {
28         if(p&1)    base=base*a;
29         a=a*a;
30         p>>=1;    
31     }
32     return base;
33 }
34 int main()
35 {
36 //    freopen("maximum.in","r",stdin);
37 //    freopen("maximum.out","w",stdout);
38     n=read();
39     if(n<=0)
40     {
41         for(LL i=1;i<=n;i++)    a[i]=read();
42         scanf("%s",s);
43         LL ls=strlen(s);
44         for(LL i=0;i<=ls-1;i++)
45             if(s[i]=='1')    
46                 m+=fastpow(2,i);
47         LL ans=0;
48         for(LL i=1;i<=m;i++)
49         {
50             LL p=i,now=0;
51             for(LL j=0;j<=31;j++)
52                 if(p&(1<<j))
53                     now+=a[j+1];
54         //    cout<<now<<endl;
55             ans=max(ans,now);
56         }
57         printf("%lld",ans);
58     }
59     else
60     {
61         for(LL i=0;i<n;i++)    a[i]=read();
62         for(LL i=0;i<n;i++)
63         {
64             dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
65             dp[i][1]=max(dp[i][0],dp[i][0]+a[i]);
66         }
67         //for(LL i=0;i<n;i++)    printf("%d ",dp[i][0]);printf("\n");
68         //for(LL i=0;i<n;i++)    printf("%d ",dp[i][1]);printf("\n");
69         scanf("%s",s);
70         LL ls=strlen(s);
71         LL now=0;// 已经选了的限制位
72         LL ans=0; 
73         for(LL i=ls-1;i>=0;i--)
74         {
75             if(s[i]=='1')//最高位
76             {
77                 flag=1;
78                 ans=max(ans,max( dp[i-1][0] ,dp[i-1][1]) +now);
79                 if(a[i]>0)    now+=a[i];
80             }
81             else if(flag==1) ans=max(ans,max(dp[i][0],dp[i][1]));
82         }
83         ans=max(ans,now);
84         printf("%lld",ans);        
85     }
86     return 0;
87 }
88 
89 
90 /*
91 
92 4
93 -1 1 2 0
94 0010
95 
96 //2
97 */

View Code

T2

考场上推出一个很逗比的结论，

首先二分一个值，对于每一个点，如果要修改的话，那么now+val,now,now-val这三个值一定有一个是最优的。

这个用dp应该能水60分。。。

不过没时间写了，打了25的暴力

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #define LL long long 
  8 using namespace std;
  9 const LL MAXN=1e6+10;
 10 const LL INF=0x7fffff;
 11 inline LL read()
 12 {
 13     char c=getchar();LL flag=1,x=0;
 14     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
 15     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;
 16 }
 17 LL n,k;
 18 LL ans=0,maxval=-INF,minval=INF;
 19 LL a[MAXN];
 20 LL dfs(LL now,LL val,LL spend)
 21 {
 22     if(spend>k)    return 0;
 23     if(now==n)
 24     {
 25         LL now=-INF;
 26         for(LL i=1;i<=n-1;i++)
 27             now=max(now,abs(a[i]-a[i+1]));
 28         if(now<=val)    return 1;
 29         return 0;
 30     }
 31     if(abs(a[now+1]-a[now])>val)
 32     {
 33         LL pre=a[now+1];
 34         a[now+1]=a[now]+val;
 35         if( dfs(now+1,val,spend+1) )    return 1;
 36         a[now+1]=a[now];
 37         if( dfs(now+1,val,spend+1) )    return 1;
 38         a[now+1]=a[now]-val;
 39         if( dfs(now+1,val,spend+1) )    return 1;
 40         a[now+1]=pre;
 41     }
 42     if(dfs(now+1,val,spend))    return 1;
 43     return 0;
 44 }
 45 LL check(LL val)//最小值 
 46 {
 47     LL now=1,spend=0;
 48     if(abs(a[1]-a[2])>val)
 49     {
 50         if(k==0)    return 0;
 51         LL pre=a[1];
 52         a[1]=a[2]+val;    if( dfs(now+1,val,spend+1) )    return 1;
 53         a[1]=a[2];        if( dfs(now+1,val,spend+1) )    return 1;
 54         a[1]=a[2]-val;    if( dfs(now+1,val,spend+1) )    return 1;
 55         a[1]=pre;        
 56         if( dfs(now,val,spend) )    return 1;
 57     }
 58     else    if( dfs(now+1,val,0) )    return 1;
 59     return 0;
 60 }
 61 int main()
 62 {
 63 //    freopen("minimum.in","r",stdin);
 64 //    freopen("minimum.out","w",stdout);
 65     n=read();k=read();
 66     if(k>=n-1)    
 67     {
 68         printf("0");return 0;
 69     }
 70     for(LL i=1;i<=n;i++)    a[i]=read(),maxval=max(a[i],maxval),minval=min(minval,a[i]);
 71     LL l=0,r=maxval-minval;
 72     LL ans=0;
 73     while(l<=r)
 74     {
 75         LL mid=l+r>>1;
 76         if(check(mid))    ans=mid,r=mid-1;
 77         else l=mid+1;
 78     }
 79     printf("%lld",ans);
 80     return 0;
 81 }
 82 
 83 
 84 /*
 85 
 86 5 2
 87 1 2 1 2 1
 88 //0
 89 
 90 
 91 5 1
 92 1 3 1 2 1
 93 //1
 94 
 95 2 0
 96 1 4
 97 //3
 98 
 99 4 1
100 1 3 5 7 
101 //2
102 
103 4 3
104 1 3 5 7 
105 //0
106 
107 4 2
108 1 3 5 7 
109 //2
110 */