2018百度星初戦:1003度熊の切り紙
1954 ワード
テーマリンク:http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=825&pid=1003
この問題は本当に素晴らしいです.私は基本的にこの問題を2時間かけて6回も書きました.精力は全部使ったことがあります.これは問題です.
まず、例を挙げます.
15 4
111011001111001001
1:まずこれをこう分けましょう.
1:111 2:11 3:00 4:1111 5:001
私たちは最大効率の文字列を求めて、単独でいくつかのすべての1のフィールドを減らすことができます.残りは後ろに置く.例えば、この問題は組み合わせられます.
2 4 1 3 5
この中で3つの部分に分けられます.第一部分は2と4、第二部分は1、第三部分は3と5です.
第1の部分は全部1であり、第2の部分は1であり、第3の部分は任意である.
最大プレフィックスは基本的にこのように長いです.
以上の分析を経て、次はこの3つの部分を探すべきです.
その中でまずこのように分割します.
111 11 1111 1
注意すべき点は、最初の尾が0だったら、0を首位に置いて、中間の0を無視してもいいです.例えば、0010100は00、11、00に分けるべきです.
それから、第二部は第一段を取ります.切断しないで、他は一回切ります.
第一部分は第一段では取りません.そして中間を取ると二回カットが必要です.
次はよく解決します.まず第一段と最後の段を考えずに、まず中間で第一部分を取って、二回カットします.
2回のカットで一部分を切ることができます.
貪欲は最大値を取る1111.
そして私達は二回カットがあります.3つの選択方法があります.
1:第二段は第二部分で、端は第一部分に加算されます.
2:最初の部分は第一の部分で、第二の部分は第一の部分に加えます.
3:最初の部分は第一部分で、最後の部分は第一部分に加えます.
そしてコードが実現されました.
この問題は本当に素晴らしいです.私は基本的にこの問題を2時間かけて6回も書きました.精力は全部使ったことがあります.これは問題です.
まず、例を挙げます.
15 4
111011001111001001
1:まずこれをこう分けましょう.
1:111 2:11 3:00 4:1111 5:001
私たちは最大効率の文字列を求めて、単独でいくつかのすべての1のフィールドを減らすことができます.残りは後ろに置く.例えば、この問題は組み合わせられます.
2 4 1 3 5
この中で3つの部分に分けられます.第一部分は2と4、第二部分は1、第三部分は3と5です.
第1の部分は全部1であり、第2の部分は1であり、第3の部分は任意である.
最大プレフィックスは基本的にこのように長いです.
以上の分析を経て、次はこの3つの部分を探すべきです.
その中でまずこのように分割します.
111 11 1111 1
注意すべき点は、最初の尾が0だったら、0を首位に置いて、中間の0を無視してもいいです.例えば、0010100は00、11、00に分けるべきです.
それから、第二部は第一段を取ります.切断しないで、他は一回切ります.
第一部分は第一段では取りません.そして中間を取ると二回カットが必要です.
次はよく解決します.まず第一段と最後の段を考えずに、まず中間で第一部分を取って、二回カットします.
2回のカットで一部分を切ることができます.
貪欲は最大値を取る1111.
そして私達は二回カットがあります.3つの選択方法があります.
1:第二段は第二部分で、端は第一部分に加算されます.
2:最初の部分は第一の部分で、第二の部分は第一の部分に加えます.
3:最初の部分は第一部分で、最後の部分は第一部分に加えます.
そしてコードが実現されました.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
Scanner sc=new Scanner(System.in);
int arr[]=new int[10000]; //arr 1 , 0
while(sc.hasNext()) {
int n=sc.nextInt();
int k=sc.nextInt();
int len=0;
String s=sc.next();
n=s.length();
for(int i=0;i2) { //
if(k%2==0) {
sum+=arr[0]+arr[len-1]+arr[len-2-t];
sum-=Math.min(arr[0], Math.min(arr[len-t-2], arr[len-1]));
}
else {
sum+=Math.max(arr[0]+arr[len-1], arr[len-t-2]);
}
}
else {
sum+=arr[0];
if(k>=1)
sum+=arr[len-1];
}
System.out.println(sum);
}
}
}