Day6下午题解1

预计分数：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维护

转移也比较好写

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const LL MAXN=1e6+;

 const LL INF=0x7fffff;

 inline LL read()

 {

     char c=getchar();LL flag=,x=;

     while(c<''||c>'')    {if(c=='-')    flag=-;c=getchar();}

     while(c>=''&&c<='')     x=x*+c-,c=getchar();return x*flag;

 }

 LL n,m;

 char s[MAXN];

 LL a[MAXN];

 LL maxpos;//最高位的位置

 LL dp[MAXN][];

 bool flag=;

 LL fastpow(LL a,LL p)

 {

     LL base=;

     while(p)

     {

         if(p&)    base=base*a;

         a=a*a;

         p>>=;

     }

     return base;

 }

 int main()

 {

 //    freopen("maximum.in","r",stdin);

 //    freopen("maximum.out","w",stdout);

     n=read();

     if(n<=)

     {

         for(LL i=;i<=n;i++)    a[i]=read();

         scanf("%s",s);

         LL ls=strlen(s);

         for(LL i=;i<=ls-;i++)

             if(s[i]=='')

                 m+=fastpow(,i);

         LL ans=;

         for(LL i=;i<=m;i++)

         {

             LL p=i,now=;

             for(LL j=;j<=;j++)

                 if(p&(<<j))

                     now+=a[j+];

         //    cout<<now<<endl;

             ans=max(ans,now);

         }

         printf("%lld",ans);

     }

     else

     {

         for(LL i=;i<n;i++)    a[i]=read();

         for(LL i=;i<n;i++)

         {

             dp[i][]=max(dp[i-][],dp[i-][]);

             dp[i][]=max(dp[i][],dp[i][]+a[i]);

         }

         //for(LL i=0;i<n;i++)    printf("%d ",dp[i][0]);printf("\n");

         //for(LL i=0;i<n;i++)    printf("%d ",dp[i][1]);printf("\n");

         scanf("%s",s);

         LL ls=strlen(s);

         LL now=;// 已经选了的限制位

         LL ans=;

         for(LL i=ls-;i>=;i--)

         {

             if(s[i]=='')//最高位

             {

                 flag=;

                 ans=max(ans,max( dp[i-][] ,dp[i-][]) +now);

                 if(a[i]>)    now+=a[i];

             }

             else if(flag==) ans=max(ans,max(dp[i][],dp[i][]));

         }

         ans=max(ans,now);

         printf("%lld",ans);

     }

     return ;

 }

 /*

 4

 -1 1 2 0

 0010

 //2

 */

T2

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

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

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const LL MAXN=1e6+;

 const LL INF=0x7fffff;

 inline LL read()

 {

     char c=getchar();LL flag=,x=;

     while(c<''||c>'')    {if(c=='-')    flag=-;c=getchar();}

     while(c>=''&&c<='')     x=x*+c-,c=getchar();return x*flag;

 }

 LL n,k;

 LL ans=,maxval=-INF,minval=INF;

 LL a[MAXN];

 LL dfs(LL now,LL val,LL spend)

 {

     if(spend>k)    return ;

     if(now==n)

     {

         LL now=-INF;

         for(LL i=;i<=n-;i++)

             now=max(now,abs(a[i]-a[i+]));

         if(now<=val)    return ;

         return ;

     }

     if(abs(a[now+]-a[now])>val)

     {

         LL pre=a[now+];

         a[now+]=a[now]+val;

         if( dfs(now+,val,spend+) )    return ;

         a[now+]=a[now];

         if( dfs(now+,val,spend+) )    return ;

         a[now+]=a[now]-val;

         if( dfs(now+,val,spend+) )    return ;

         a[now+]=pre;

     }

     if(dfs(now+,val,spend))    return ;

     return ;

 }

 LL check(LL val)//最小值

 {

     LL now=,spend=;

     if(abs(a[]-a[])>val)

     {

         if(k==)    return ;

         LL pre=a[];

         a[]=a[]+val;    if( dfs(now+,val,spend+) )    return ;

         a[]=a[];        if( dfs(now+,val,spend+) )    return ;

         a[]=a[]-val;    if( dfs(now+,val,spend+) )    return ;

         a[]=pre;

         if( dfs(now,val,spend) )    return ;

     }

     else    if( dfs(now+,val,) )    return ;

     return ;

 }

 int main()

 {

 //    freopen("minimum.in","r",stdin);

 //    freopen("minimum.out","w",stdout);

     n=read();k=read();

     if(k>=n-)

     {

         printf("");return ;

     }

     for(LL i=;i<=n;i++)    a[i]=read(),maxval=max(a[i],maxval),minval=min(minval,a[i]);

     LL l=,r=maxval-minval;

     LL ans=;

     while(l<=r)

     {

         LL mid=l+r>>;

         if(check(mid))    ans=mid,r=mid-;

         else l=mid+;

     }

     printf("%lld",ans);

     return ;

 }

 /*

 5 2

 1 2 1 2 1

 //0

 5 1

 1 3 1 2 1

 //1

 2 0

 1 4

 //3

 4 1

 1 3 5 7

 //2

 4 3

 1 3 5 7

 //0

 4 2

 1 3 5 7

 //2

 */

T3

分块瞎搞。。

巴特西

Day6下午题解1

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

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

T1

T2

T3

最新文章

热门文章