预计分数：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
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             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<
            
             =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 493 -1 1 2 094 001095 96 //297 */
            
           
          
         
        
       
      

 

T2

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

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

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

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

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             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 1100 1 3 5 7 101 //2102 103 4 3104 1 3 5 7 105 //0106 107 4 2108 1 3 5 7 109 //2110 */
           
          
         
        
       
      

 

 

 

T3

分块瞎搞。。