省流：\(100+0+0+8=108\)
简称：唐诗
T1
T2
T2 很有思路，几分钟就推出来一个 \(a_i\) 不全为奇数的柿子，然后发现大样例是全为奇数的（）
然后就一直在推式子，然后快推完了比赛结束了……
然后赛后发现全为奇数的用暴力搞……
T3
一眼 DP 但是想写 T2，甚至连暴力都没码……
正解是状压（一位大佬的）：
f[0][0]=g[n+1][0][0]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<16;++j) val[i][j]=-((j>>3)&1)*a[i].y+((j>>2)&1)*a[i].y-((j>>1)&1)*a[i].x+(j&1)*a[i].x+a[i].w;
for(int j=0;j<16;++j){
f[i][j]=f[i-1][j]+a[i].w;
for(int s=j;s;s=(s-1)&j) f[i][j]=max(f[i][j],f[i-1][j^s]+val[i][s]);
}
}
for(int i=n;i;--i)
for(int k=0;k<=4;++k)
for(int j=0;j<16;++j){
g[i][k][j]=g[i+1][k][j];
for(int s=j;s;s=(s-1)&j) g[i][k][j]=max(g[i][k][j],g[i+1][k-1][j^s]+val[i][s]);
}
while(q--){
int x;ll res=0;
scanf("%d",&x);
for(int i=x;i>=x-4&&i>=0;--i) for(int j=0;j<16;++j) res=max(res,f[i][15^j]+g[i+1][x-i][j]);
printf("%lld\n",res);
}
T4
感觉不会写就看了两眼，赛后发现可以人类智慧，然后就是裸线段树了……
总结
-
T2 浪费过多时间
-
就算懒也要打暴力
-
注意时间
-
要有敏感性