`
qingtangpaomian
  • 浏览: 37409 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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);
			}
		}
	}
	
}


 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics