D~F Java题解,代码已去除冗余~~~
删除一个长度为2或者3的段,等同于删除若干长度不为1的段,因此直接常规动态规划即可,时间 =复杂度O(Tn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
int n=sc.nextInt();
long max[]=new long[n+1];
for(int j=1;j<=n;j++){
max[j]=Math.max(sc.nextInt()+max[j-1],Math.max(j>=2?max[j-2]:-(long)1e18,j>=3?max[j-3]:-(long)1e18));
}
System.out.println(max[n]);
}
}
}
拆位分解每一位,首先为了让数字可能大,不妨将答案填充为最大int数,之后按每一比特位进行分析:x位为0,y位为0,那么n个数的这一位全为0;x位为0,y位为1,不存在这杨的组合;x位为1,y位为0,n个数中填充的位数必须为偶数位,且不能一个也不填;x位为1,y位为1,与上一种情况类似;;以上的情况34是在固定位置操作的,可能将这个位置的数字减为0,因此需要将后边某一个非单比特置为数字拆解一位过来以保证全正,时间复杂度O(TnC),C==31
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
int n=sc.nextInt(),x=sc.nextInt(),y=sc.nextInt(),ans[]=new int[n];
Arrays.fill(ans,Integer.MAX_VALUE);
boolean found=(x&y)==y;
for(int j=30;j>=0&&found;j--){
int a=x>>j&1,b=y>>j&1;
if(a==0){
if(b==1){
found=false;
}
else{
for(int k=0;k<n;k++){
ans[k]^=1<<j;
}
}
}
else{
if(n%2!=b){
if(n==1){
found=false;
}
ans[0]^=1<<j;
}
}
}
if(ans[0]==0){
found=false;
for(int j=1;j<n;j++){
if(Integer.bitCount(ans[j])>1){
ans[0]=ans[j]&-ans[j];
ans[j]&=ans[j]-1;
found=true;
break;
}
}
}
if(!found){
System.out.println("NO");
}
else{
System.out.println("YES");
for(int a:ans){
System.out.print(a+" ");
}
System.out.println();
}
}
}
}
最优的情况一定是将字符创分为三段,分别将问号填充为“ovo”,容易证明,交换相邻段的任意两个问号的取值并不会使得答案更优,因此枚举分界点即可,时间复杂度O(Tn^3)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
String s=sc.next();
int n=s.length(),pre[][]=new int[n+1][3],ans=0;
for(int j=1;j<=n;j++){
pre[j]=pre[j-1].clone();
pre[j][findIdx(s.charAt(j-1))]++;
}
for(int j=0;j<=n;j++){
for(int k=j;k<=n;k++){
int count=0;
//[1,j,'o'],[j+1,k,'v],[k+1,n,'o']
for(int p=1;p<=n;p++){
count+=p<=j&&s.charAt(p-1)=='v'?(find(pre,'o',0,p-1)+find(pre,'?',0,p-1))*(find(pre,'o',p,j)+find(pre,'?',p,j)+find(pre,'o',j,k)+find(pre,'o',k,n)+find(pre,'?',k,n)):p>j&&p<=k&&s.charAt(p-1)!='o'?(find(pre,'o',0,j)+find(pre,'?',0,j)+find(pre,'o',j,p-1))*(find(pre,'o',p,k)+find(pre,'o',k,n)+find(pre,'?',k,n)):p>k&&s.charAt(p-1)=='v'?(find(pre,'o',0,j)+find(pre,'?',0,j)+find(pre,'o',j,k)+find(pre,'o',k,p-1)+find(pre,'?',k,p-1))*(find(pre,'o',p,n)+find(pre,'?',p,n)):0;
}
ans=Math.max(ans,count);
}
}
System.out.println(ans);
}
}
static int find(int pre[][],char c,int l,int r){
return pre[r][findIdx(c)]-pre[l][findIdx(c)];
}
static int findIdx(char c){
return c=='o'?0:c=='v'?1:2;
}
}