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:最初の部分は第一部分で、最後の部分は第一部分に加えます.
そしてコードが実現されました. 
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);
			}
	}
}