USACO - 3.2.2 - Stringsobits

 

原创文章转载请注明出处

摘要：动态规划  ， 三星题目

一. 题目翻译

1. 描述：

  考虑排好序的N(N<=31)位二进制数。

          你会发现，这很有趣。因为他们是排列好的，而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。

          你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的（注：题目这里表述不清，实际是，从最小的往大的数，数到第i个符合条件的，这个意思），长度为N，且1的位数的个数小于等于L的那个二进制数。

          （例：100101中，N=6，含有位数为1的个数为3）。

2. 格式：

          INPUT FORMAT:

          (file kimbits.in)

          共一行，用空格分开的三个整数N，L，i。

          OUTPUT FORMAT:

          (file kimbits.out)

          共一行，输出满足条件的第i小的二进制数。.

3. SAMPLE：

          SAMPLE INPUT:

5 3 19

          SAMPLE OUTPUT:

10011

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          分析题目的意思是要输出一个二进制数，这个二进制数是要求在长度为N，且1的位数个数小于等于L的二进制数中第i大数。那么首先我们要先确定到底符合要求的长度为N，且1的位数小于等于L的二进制数有多少个？解决这个问题，我们可以使用动态规划。

          dp[k][j]表示长度为k的二进制数中，1的个数为j的二进制数的个数。状态转移方程，dp[k][j] = dp[k-1][j] + dp[k-1][j](第k位取0和取1两种情况)。之后循环累加dp[k][j](j=1..L)，使得dp[k][j]表示长度为k的二进制数，1的个数小于等于j的二进制数的个数。

          有了dp[k][j]后构造所求的字符串呢 ？

          设所求串为sb，sb中的第n位如果取0，那么dp[n-1][l] >=i(l表示字符串包含的1的个数，i表示第几个取值) ；如果sb中的第n位取1，那么dp[n-1][l]<i。（这里思考下为什么？dp[n][l] = dp[n-1][l] + dp[n-1][l-1]，dp[n-1][l]表示当前位为0的情况）。

 

2. 具体实现（具体实现过程中出现的问题）：

          这里详细描述下有了dp[k][j]后构造字符串sb的过程。

          // i表示所求的字符串为排序中的第i个， n表示要生成的字符串的长度 ， L表示要生成字符串当中1的个数

           if (i<=dp[n-1][L]) 

               sb.append(0);

               继续递归(第i位，n-1  ，L);// 第n位必须是“0”，继续递归寻找。字符串长度减1。字符串中1的个数不变

          else 

               sb.append(1);

               继续递归(i-dp[n-1][L] ，n-1 ， L-1); //第n位是“1”，所以减去第k位是0的字符串的个数。字符串的长度减1。字符串中1的个数也减1.

3. 启示:

            这道题目是非常有意思并且值得思考的，题目不可以直接由动态规划求出答案，而是对动态规划后的结果进一步利用，最终产生答案，很有意思。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:kimbits
*/
package session_3_2_2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class kimbits{

	public static void main(String[] args) throws Exception {
//		Scanner in = new Scanner(new BufferedReader(new FileReader(
//		"kimbits.in")));
//		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
//		"kimbits.out")));
		
		Scanner in = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int N = in.nextInt();
		int L = in.nextInt();
		long i = in.nextLong();
		
		long[][] dp = new long[N+1][L+1];
		dp[0][0] = 1;
		for (int k=1;k<=N;k++){
			for (int j=0;j<=L;j++){
				if (j-1>=0)
					dp[k][j] = dp[k-1][j] + dp[k-1][j-1];
				else 
					dp[k][j] = dp[k-1][j];
			}
		}
		
		for (int k=0;k<=N;k++){
			for (int j=1;j<=L;j++){
				dp[k][j] += dp[k][j-1];
			}
		}
		
		StringBuilder sb = new StringBuilder();
		execute(i, dp, N, L, sb);
		pw.println(sb);
		pw.close();
	}
	
	public static void execute(long i,long[][] dp, int n ,int l ,StringBuilder sb){
		if (n>=1){
			if (i<=dp[n-1][l]){
				sb.append(0);
				execute(i, dp, n-1, l, sb);
			} else {
				sb.append(1);
				execute(i-dp[n-1][l], dp, n-1, l-1, sb);
			}
		}
	}
	
}