给你一个由若干 0 和 1 组成的字符串s,请你计算并返回将该字符串分割成两个子字符串(即左子字符串和右子字符串, 子字符串允许为空)所能获得的最大得分。
已知分割字符串的得分规则如下:左子字符串中:0得2分,1得1分
右子字符串中:1得2分,0得1分
子字符串为空则得0分
一行包括一个由0和1组成的字符串s
一行一个整数表示答案。
011101
11
当左子字符串 = "0" 且 右子字符串 = "11101",得分最大= 2+ 9 = 11
00111
10
当左子字符串 = "00" 且右子字符串 = "111" 时,得分最大 = 4 + 6 = 10
#include<iostream> #include<string> using namespace std; int maxScore(string s){ int maxres=0; int maxnum=0; for(int i=0;i<s.size();i++){ //右字串总和 if(s[i]=='0') maxnum++; else maxnum+=2; } maxres=max(maxnum,maxres); for(int i=0;i<s.size();i++){ //滑动窗口 if(s[i]=='0') maxnum++; else maxnum--; maxres=max(maxnum,maxres); } return maxres; } int main(){ string s; cin>>s; cout<<maxScore(s)<<endl; }
#include <iostream> #include <string> using namespace std; long long leftSocore( char ch ){ if( ch == '0') return 2; if( ch == '1') return 1; return 0; } long long rightSocore( char ch ){ if( ch == '0') return 1; if( ch == '1') return 2; return 0; } int main( ){ string str; getline(cin,str); if( str.size() == 0 ) return 0; long long left_score = 0; long long right_score = 0; long long max_score = 0; for( int i = 0; i < str.size(); i++ ){ right_score += rightSocore( str[i] ); } max_score = right_score; for( int i = 0; i < str.size(); i++ ){ left_score += leftSocore( str[i] ); right_score -= rightSocore( str[i] ); if( left_score + right_score > max_score ){ max_score = left_score + right_score; } } cout<<max_score; return 0; }
#include <iostream> using namespace std; int main() { string s; cin >> s; int cur = 0; for(char c : s) { if(c == '0') { cur += 1; } else { cur += 2; } } int result = cur; for(char c : s) { if(c == '0') { cur++; } else { cur--; } result = max(result,cur); } cout << result; return 0; }
#include <bits/stdc++.h> using namespace std; int main(){ string str; cin >> str; // 双向遍历 vector<int> l_val(str.size()), r_val(str.size()); for(int i = 0; i < str.size(); ++i){ if(i == 0){ l_val[i] = (str[i] == '0' ? 2 : 1); }else{ if(str[i] == '0'){ l_val[i] = l_val[i - 1] + 2; }else{ l_val[i] = l_val[i - 1] + 1; } } } for(int i = str.size() - 1; i >= 0; --i){ if(i == str.size() - 1){ r_val[i] = (str[i] == '1' ? 2 : 1); }else{ if(str[i] == '0'){ r_val[i] = r_val[i + 1] + 1; }else{ r_val[i] = r_val[i + 1] + 2; } } } int ans = r_val[0]; for(int i = 0; i < str.size(); ++i){ ans = max(l_val[i] + (i + 1 == str.size() ? 0 : r_val[i + 1]), ans); } ans = max(ans, l_val[str.size() - 1]); cout << ans << endl; return 0; }思路是自左向右求一遍以当前字符为分界的左边字符串的得分,再自右向左求一边,然后去对于每个字符将左边和右边的之加起来取最大即可。
import java.util.Arrays; import java.util.Scanner; /** * @author asdf */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String next = scanner.next(); if (next.length() == 0) { System.out.println(0); return; } String left = ""; String right = ""; int sum = 0; int[] arr = new int[next.length() + 1]; for (int i = 1; i < next.length(); i ++) { left = next.substring(0, i); right = next.substring(i); for (char c : left.toCharArray()) { if ('0' == c) { sum += 2; } else if ('1' == c){ sum += 1; } else { sum += 0; } } for (char c : right.toCharArray()) { if ('0' == c) { sum += 1; } else if ('1' == c){ sum += 2; } else { sum += 0; } } arr[i - 1] = sum; sum = 0; } for (char c : next.toCharArray()) { if ('0' == c) { sum += 2; } else if ('1' == c){ sum += 1; } else { sum += 0; } } arr[arr.length - 2] = sum; sum = 0; for (char c : next.toCharArray()) { if ('0' == c) { sum += 1; } else if ('1' == c){ sum += 2; } else { sum += 0; } } arr[arr.length - 1] = sum; Arrays.sort(arr); System.out.println(arr[arr.length - 1]); } }
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); int len=s.length(); int[]d=new int[len+1]; for(int i=0;i<len;i++) { if(s.charAt(i)=='0') { d[0]+=1; } else { d[0]+=2; } } for(int i=0;i<len;i++) { if(s.charAt(i)=='0') { d[i+1]=d[i]+1; } else { d[i+1]=d[i]-1; } } Arrays.sort(d); System.out.print(d[len]); } }
s=input() n=len(s) left=[0 for _ in range(n)] right=[0 for _ in range(n)] for i in range(n): if s[i]=='0': left[i]+=2 else: left[i]+=1 if i>=1:left[i]+=left[i-1] for i in range(n-1,-1,-1): if s[i]=='0': right[i]+=1 else: right[i]+=2 if i<=n-2:right[i]+=right[i+1] ret=0 for i in range(n-1): ret=max(ret,left[i]+right[i+1]) ret=max(ret,left[-1],right[0]) print(ret)不得不说有很多题都是从前往后遍历一次,再从后往前遍历一次,保存点什么,最后再遍历一次,就能做
ss=input().strip() if len(ss)==1: #特例 print(2) else: maxC=0 i=1 for i in range(len(ss)+1): #i为左子串的长度 L=[] R=[] j=0 k=i while(j<i): #左字串 L.append(ss[j]) j=j+1 while(k<len(ss)): #右字串 R.append(ss[k]) k=k+1 c=0 c=L.count('0')*2+L.count('1') c=c+R.count('1')*2+R.count('0') maxC=max(maxC,c) print(maxC)
#include<iostream> usingnamespacestd; intmain() { string str; while(cin>>str); intret=0, sum=0; for(auto j :str) {if(j=='1') {ret+=2;} else{ret+=1;}} for(inti=0;i<str.size();i++) { intcur=0, sum=0; while(cur<=i) { if(str[cur++]=='0') {sum+=2;} else{sum+=1;} } cur = i+1; while(cur<str.size()) { if(str[cur++]=='1') {sum+=2;} else {sum+=1;} } if(sum>ret) {ret = sum;} } cout<<ret; return0; } |