预计分数：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维护
转移也比较好写
代码语言：javascript复制 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 */T2
考场上推出一个很逗比的结论，
首先二分一个值，对于每一个点，如果要修改的话，那么now val,now,now-val这三个值一定有一个是最优的。
这个用dp应该能水60分。。。
不过没时间写了，打了25的暴力
代码语言：javascript复制 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 */
T3
分块瞎搞。。
