Monthly Archives: April 2017

LeetCode Optimal Division

LeetCode Optimal Division
Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.
However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.
Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant,
since they don't influence the operation priority. So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Note:

  1. The length of the input array is [1, 10].
  2. Elements in the given array will be in range [2, 1000].
  3. There is only one optimal division for each test case.

给定一个正整数数组,数据范围是[2,1000],初始每个数依次除以后一个数,现在要给数组加上括号,使得整个数组相除的结果最大。
首先来个暴力方法,对区间[start, end],枚举每一个分割位置i,也就是[start, i]算除法,[i+1, end]也算除法,然后把前者的结果除以后者。结果的最大值为前者的最大值除以后者的最小值,结果的最小值为前者的最小值除以后者的最大值。一直递归下去,最后就能得到整个区间[0,n-1]的最大值了。
代码如下:

struct T {
	double lfMax, lfMin;
	string strMax, strMin;
};
class Solution {
private:
	T optimal(vector<int>& nums, int start, int end){
		T t;
		if(start == end){
			t.lfMax = t.lfMin = nums[start];
			t.strMax = t.strMin = to_string(nums[start]);
			return t;
		}
		t.lfMax = std::numeric_limits<double>::min();
		t.lfMin = std::numeric_limits<double>::max();
		for(int i = start; i < end; ++i){
			T tl = optimal(nums, start, i);
			T tr = optimal(nums, i + 1, end);
			if(tl.lfMax / tr.lfMin > t.lfMax){
				t.lfMax = tl.lfMax / tr.lfMin;
				t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : "");
			}
			if(tl.lfMin / tr.lfMax < t.lfMin){
				t.lfMin = tl.lfMin / tr.lfMax;
				t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : "");
			}
		}
		return t;
	}
public:
    string optimalDivision(vector<int>& nums) {
    	T t = optimal(nums, 0, nums.size() - 1);
    	return t.strMax;
    }
};

本代码提交AC,用时86MS。暴力方法相当于枚举数组的所有排列情况,时间复杂度为O(n!)。
上述方法对某一小段区间会有很多重复计算,我们可以用数组把结果存起来达到加速的目的。使用数组memo[i][j]存储[i,j]的最大值最小值结果,递归的时候如果发现memo[start][end]已经有结果了,则直接返回。代码如下:

struct T {
	double lfMax, lfMin;
	string strMax, strMin;
};
class Solution {
private:
	T optimal(vector<int>& nums, int start, int end, vector<vector<T>>& memo){
		if(memo[start][end].strMax != "" || memo[start][end].strMin != "") return memo[start][end];
		T t;
		if(start == end){
			t.lfMax = t.lfMin = nums[start];
			t.strMax = t.strMin = to_string(nums[start]);
			memo[start][end] = t;
			return t;
		}
		t.lfMax = std::numeric_limits<double>::min();
		t.lfMin = std::numeric_limits<double>::max();
		for(int i = start; i < end; ++i){
			T tl = optimal(nums, start, i, memo);
			T tr = optimal(nums, i + 1, end, memo);
			if(tl.lfMax / tr.lfMin > t.lfMax){
				t.lfMax = tl.lfMax / tr.lfMin;
				t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : "");
			}
			if(tl.lfMin / tr.lfMax < t.lfMin){
				t.lfMin = tl.lfMin / tr.lfMax;
				t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : "");
			}
		}
		memo[start][end] = t;
		return t;
	}
public:
    string optimalDivision(vector<int>& nums) {
    	vector<vector<T>> memo(nums.size(), vector<T>(nums.size()));
    	T t = optimal(nums, 0, nums.size() - 1, memo);
    	return t.strMax;
    }
};

本代码提交AC,用时6MS。一下快了不少。
还有一种纯数学的方法。假设我们要对a/b/c/d加括号使得结果最大,则a肯定是分子不能动了,那么就相当于最小化b/c/d。b/c/d有两种加括号的方案:b/(c/d)和(b/c)/d。如果令b/(c/d)>b/c/d,因为b,c,d都是正数,推出d>1。又题目中的数据范围是[2,1000],所以b/(c/d)>b/c/d显然成立。也就是b/c/d这种方案是最小的,使得a/(b/c/d)结果最大。所以只需要把a后面的数加一个括号整体括起来就好了。
代码如下:

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
    	int n = nums.size();
    	if(n == 1) return to_string(nums[0]);
    	else if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
    	string ans = to_string(nums[0]) + "/(";
    	for(int i = 1; i < n - 1; ++i){
    		ans += to_string(nums[i]) + "/";
    	}
    	return ans + to_string(nums[n-1]) + ")";
    }
};

本代码提交AC,用时3MS。
参考:https://leetcode.com/articles/optimal-division/

LeetCode Binary Tree Tilt

LeetCode Binary Tree Tilt
Given a binary tree, return the tilt of the whole tree.
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.
The tilt of the whole tree is defined as the sum of all nodes' tilt.
Example:

Input:
         1
       /   \
      2     3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

  1. The sum of node values in any subtree won't exceed the range of 32-bit integer.
  2. All the tilt values won't exceed the range of 32-bit integer.

定义二叉树一个节点的tilt为其左子树元素之和与右子树元素之和的差的绝对值。整棵二叉树的tilt为所有节点的tilt之和。现在要求一棵二叉树的tilt。
简单题,递归求解元素之和,然后更新tilt。都是递归到叶子节点,然后累加和往父亲节点走。
代码如下:

class Solution {
private:
	void dfs(TreeNode* root, int& sum, int& tilt){
		if(root == NULL) {
			sum = 0;
			tilt = 0;
		} else {
			int lsum = 0, rsum = 0, ltilt = 0, rtilt = 0;
			dfs(root->left, lsum, ltilt);
			dfs(root->right, rsum, rtilt);
			sum = lsum + rsum + root->val;
			tilt = ltilt + rtilt + abs(lsum - rsum);
		}
	}
public:
    int findTilt(TreeNode* root) {
    	int sum = 0, tilt = 0;
    	dfs(root, sum, tilt);
    	return tilt;
    }
};

本代码提交AC,用时16MS。

LeetCode Array Partition I

LeetCode Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

给定一个长度为2n的数组,要求把数组分成n组,即(a1, b1), (a2, b2), ..., (an, bn) ,使得每组的最小值之和最大。
使用贪心策略,比如样例中,4和3肯定不能和1配对,因为1肯定是最小的,不能拿很大的数和1陪葬,所以只拿2和1配对;然后3、4配对。所以规律就是对数组排序,从小到大每两个配对。那么每组最小值之和就是第0、2、4...个数之和。
代码如下:

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
    	sort(nums.begin(), nums.end());
    	int ans = 0;
    	for(int i = 0; i < nums.size(); i += 2) ans += nums[i];
    	return ans;
    }
};

本代码提交AC,用时92MS。

LeetCode Student Attendance Record II

LeetCode Student Attendance Record II
Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.
A student attendance record is a string that only contains the following three characters:

  1. 'A' : Absent.
  2. 'L' : Late.
  3. 'P' : Present.

A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
Example 1:

Input: n = 2
Output: 8
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times.

Note: The value of n won't exceed 100,000.


上一题的基础上增大了难度,这一题给定数组n,问长度为n的学生出席字符串,有多少种可能让该学生获奖。
显然是DP问题,不过是三维DP。令dp[n][i][j]表示长度为n的字符串,包含i个'A'并且以j个'L'结尾的字符串个数。那么有如下的递推公式:
dp[n][0][0]=sum(dp[n-1][0]):要求长度为n、包含0个'A',且以0个'L'结尾的字符串个数;所以前n-1肯定也只包含0个'A',但是前n-1可以以0、1或2个'L'结尾,因为我第n个字符不放'L'就能保证前n以0个'L'结尾。所以dp[n][0][0]=sum(dp[n-1][0])。其他的类似分析有:

  • dp[n][0][1]=dp[n-1][0][0]
  • dp[n][0][2]=dp[n-1][0][1]
  • dp[n][1][0]=sum(dp[n-1][0])+sum(dp[n-1][1])
  • dp[n][1][1]=dp[n-1][1][0]
  • dp[n][1][2]=dp[n-1][1][1]

代码如下:

const int kMOD = 1000000007;
class Solution {
private:
	long long getSum(vector<int>& v) {
		long long ans = 0;
		for(const int &i : v) ans += i;
		return ans % kMOD;
	}
public:
    int checkRecord(int n) {
    	vector<vector<int>> dp = {{1, 1, 0}, {1, 0, 0}};
    	for(int i = 2; i <= n; ++i){
    		vector<vector<int>> ndp = {{0, 0, 0}, {0, 0, 0}};
    		ndp[0][0] = getSum(dp[0]);
    		ndp[0][1] = dp[0][0];
    		ndp[0][2] = dp[0][1];
    		ndp[1][0] = (getSum(dp[1]) + getSum(dp[0])) % kMOD;
    		ndp[1][1] = dp[1][0];
    		ndp[1][2] = dp[1][1];
    		dp = ndp;
    	}
    	return (getSum(dp[0]) + getSum(dp[1])) % kMOD;
    }
};

本代码提交AC,用时612MS。

LeetCode Student Attendance Record I

LeetCode Student Attendance Record I
You are given a string representing an attendance record for a student. The record only contains the following three characters:

  1. 'A' : Absent.
  2. 'L' : Late.
  3. 'P' : Present.

A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
You need to return whether the student could be rewarded according to his attendance record.
Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False

给定一个学生出席字符串,P表示出席了,A表示未出席,L表示迟到。如果有超过1个A或者超过2个L,则该同学不能被评奖,否则可以。先给定一个字符串,问该同学能否被评奖。
简单题,一遍扫描,记录A的数量以及连续L的数量,根据规则判断就好。
代码如下:

class Solution {
public:
    bool checkRecord(string s) {
    	int n = s.size();
    	int A = 0, L = 0;
    	for(size_t i = 0; i < n; ++i){
    		if(s[i] == 'A'){
    			++A;
    			if(A > 1) return false;
    		}
    		else if(s[i] == 'L'){
    			int tmp = 0;
    			while(i < n && s[i] == 'L'){
    				++tmp;
    				++i;
    			}
    			--i; // caution
    			L = max(tmp, L);
    			if(L > 2) return false;
    		}
    	}
    	return true;
    }
};

本代码提交AC,用时3MS。

LeetCode Longest Uncommon Subsequence I

LeetCode Longest Uncommon Subsequence I
Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.
Example 1:

Input: "aba", "cdc"
Output: 3
Explanation: The longest uncommon subsequence is "aba" (or "cdc"),
because "aba" is a subsequence of "aba",
but not a subsequence of any other strings in the group of two strings.

Note:

  1. Both strings' lengths will not exceed 100.
  2. Only letters from a ~ z will appear in input strings.

求两个字符串的最长公共子序列。以前都是用DP求最长公共子序列,现在是要求最长公共子序列。
其实很简单的一个题,如果两个字符串完全相等的话,肯定没有公共子序列的,因为A字符串的任意一个子序列一定也是B字符串的子序列,所以返回-1。但是如果A和B不相等,则可以取A,B中较长的字符串,假设是A的话,则A肯定不是B的子序列,因为A的长度大于B,而且A不等于B。
所以就很简单了,如果A和B相等的话,返回-1,否则返回A,B中较大的长度。
代码如下:

class Solution {
public:
	int findLUSlength(string a, string b) {
		return a == b ? -1 : max(a.size(), b.size());
	}
};

本代码提交AC,用时0MS。

LeetCode Reverse Words in a String III

LeetCode Reverse Words in a String III
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.


给定一个句子,要求把句子中的每个单词都逆序。
简单题,找空格,然后对每个单词reverse,直接调string::reverse或者自己写都可以。
代码如下:

class Solution {
public:
	string reverseWords(string s) {
		int i = 0, j = 0, n = s.size();
		while (j < n) {
			while (j < n&&s[j] != ' ')++j;
			reverse(s.begin() + i, s.begin() + j);
			i = ++j;
		}
		return s;
	}
};

本代码提交AC,用时23MS。

hihoCoder 1507-可疑的记录

hihoCoder 1507-可疑的记录

#1507 : 可疑的记录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一棵N个节点的树,编号1-N,其中1号节点是整棵树的根。他把这棵树的N-1条边记录成N-1行,每行2个整数a和b,表示a是b的父节点。
喜欢恶作剧的小Ho在小Hi的记录里加了一行两个整数,于是小Hi不得设法找出这行可疑的记录。具体来说,如果去掉某一行之后,余下N-1行按小Hi的规则(a是b的父节点)恰好能构成一棵N个节点的树,并且满足编号恰好是1-N且1号节点是根,那么被去掉的一行就被视为可疑的。
你能帮小Hi找出所有可疑的记录吗?

输入

第一行包含一个整数N,表示树的节点数目。
以下N行每行两个整数a和b,表示a是b的父节点。
对于30%的数据,1 <= N <= 1000
对于100%的数据, 1 <= N <= 100000, 1 <= a, b <= N
输入保证合法。

输出

输出一行包含若干个从小到大的整数,表示可疑的行号。(行号从1开始)

样例输入
3
1 2
1 3
1 3
样例输出
2 3

有一棵编号从1~N的树,其中根节点为1。这棵树的n-1条边用n-1行x y表示,其中x是y的父亲节点。现在小Ho在其中增加了一行,导致不满足上述性质,要求找出增加的那行。
这一题我用了BFS,DFS等乱七八糟的方法,最终WA。。。看过大神的代码之后,其实这题根本不需要用这些高深的策略,因为只添加了一行,所以用一些简单的规则即可找出。

  1. 首先,如果这一行x,y中y如果出现1,则这一行肯定是有问题的,因为1是根节点,不可能在右边。
  2. 其次,如果出现x==y,也有问题,因为树没有自回路。
  3. 最后,正常的树中除了根节点,每个节点有且仅有一个父亲节点,如果添加了一行,且不满足上面两种情况,则肯定会出现某个点的父亲节点有两个!所以我们只需要找出出现两个父亲节点的节点即可,而且这两个父亲都有可疑。

根据上述三条规则,马上写出代码:

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int n, x, y;
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);
	vector<int> xarry(n + 1, 0), yarry(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		scanf("%d %d", &xarry[i], &yarry[i]);
	}
	vector<vector<int>> parent(n + 1, vector<int>());
	for (int i = 0; i < n; ++i) {
		if (yarry[i] == 1) { // 根节点不可能在右边
			printf("%d\n", i + 1);
			break;
		}
		if (xarry[i] == yarry[i]) { // 没有自回路
			printf("%d\n", i + 1);
			break;
		}
		parent[yarry[i]].push_back(i + 1);
	}
	for (int i = 1; i <= n; ++i) {
		if (parent[i].size() > 1) {
			printf("%d %d ", parent[i][0], parent[i][1]);
			break; // 因为只添加了一行,所以只可能有一个节点有两个父亲
		}
	}
	return 0;
}

本代码提交AC,用时253MS。

hihoCoder 1508-剑刃风暴

hihoCoder 1508-剑刃风暴

#1508 : 剑刃风暴

时间限制:20000ms
单点时限:2000ms
内存限制:256MB

描述

主宰尤涅若拥有一招非常厉害的招式——剑刃风暴,“无论是战士还是法师,都害怕尤涅若的武士刀剑技”。
现在战场上有N名敌对英雄,他们的位置分别为(Xi, Yi),而剑刃风暴的伤害范围是一个半径为R的圆形,尤涅若可以选择一个坐标作为剑刃风暴的中心,所有处于这个圆形范围内的英雄都会受到剑刃风暴的伤害。
现在尤涅若想要知道,他的剑刃风暴最多可以同时伤害到多少敌对英雄。

输入

第一行为两个整数N和R,分别敌对英雄的数量以及剑刃风暴的半径。
接下来的N行,每行两个整数Xi和Yi,描述一个英雄的坐标。
对于30%的数据,满足1<=N<=10
对于60%的数据,满足1<=N<=100
对于100%的数据,满足1<=N<=2000, 0<=Xi, Yi<=108, 1<=R<=108,可能有两名英雄的坐标是相同的。

输出

输出一行Ans,表示尤涅若的剑刃风暴最多能够伤害到的英雄数量。

样例输入
10 2
0 10
0 10
9 10
1 2
4 5
8 8
8 4
4 2
7 7
0 7
样例输出
3

简化题意:给定平面上n个点,和一个半径为r的圆,这个圆可以任意放置,问最多能覆盖多少个点。
这题类似poj1981(单位圆),我是参考这个题解来做的。
暴力方法。最优的圆肯定是能覆盖最多的点,且有些点落在圆周上,导致这个圆只要稍微往旁边移一下,覆盖的点就会减少。所以枚举任意两个点,假设这两个点正好落在最优圆的圆周上,则由此可以确定一个圆心,然后统计所有落在这个圆内的点的个数,并更新最大值。时间复杂度是O(n^3)
有一点需要注意的是两个圆周上的点,如果它们的距离不是刚好等于直径,则能确定两个圆心,但只需算一个就好了。比如有三个点A,B,C确定的最优圆是下图中的实线,如果我们在由两点确定圆心的过程中,始终统一确定“下边”的圆,则虽然A,B确定的圆是虚线的(虽然A,B确定的圆还可以是实线,但根据我们的规定,统一取“下边”的圆),不是最优。但当遍历到A,C点对时,根据规则,这两个点确定的圆是实线的,也就是说,只要根据统一的规则确定圆心,肯定能找到那个最优圆的。

已知两点求圆心的方法请看这篇博客中的GetCenter函数,下图作了一些辅助线帮助理解。关于atan和atan2的区别,请看这篇博客

暴力方法在hiho上TLE,需要寻求更高效的算法。
假设以两个点i,j为圆心画半径为R的圆,如果两个圆相交,则在相交的弧上任意一点画圆,都能覆盖原来的i,j两点。基于这个思想,假设现在固定点i为圆心,R为半径画圆,求出所有以其他点为圆心画的圆和圆i相交的弧,则在相交重叠次数最多的那段弧上的点为圆心画的圆肯定能覆盖最多的点,覆盖的点数就是这段弧被重叠的次数。每个点i都能求出这样一个最大值,则所有点的这个最大值的最大值就是全局能覆盖的最多点。
怎样表示两个圆相交的那段弧呢,使用极坐标,因为弧是由两条半径张成的,所以可以表示成两条半径的极坐标夹角,并且标明夹角的开始(is=1)和结束(is=-1)。求重叠次数最多的弧的方法是,把所有重叠弧的起止半径的极坐标夹角排个序,然后遍历一下,当夹角开始(is=1)次数最多且结束(is=-1)次数最少时,说明重叠次数最多,所以就是is的累加和的最大值。
完整代码借鉴这篇博客,注意原代码是针对R=1的情况,如果是任意的R,则计算角差那里还需除以半径R。完整代码如下:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 2005;
const double PI = acos(-1.0);
//const double R = 1.0;//定义覆盖圆半径为R
int T, n, total, R;
struct Point {
	double x, y;
}point[MAX_N];
struct Angle {
	double data;
	int is;
	bool operator < (const Angle& rhs) const {
		return data<rhs.data;
	}
}angle[MAX_N * 2];
inline double Dis(Point a, Point b)//计算线段ab的长度
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
inline double God(Point a, Point b)//计算向量ab的极角
{
	double res = atan(fabs((b.y - a.y) / (b.x - a.x)));
	if (b.y<a.y) {
		if (b.x<a.x) res += PI;
		else res = 2 * PI - res;
	}
	else {
		if (b.x<a.x) res = PI - res;
	}
	return res;
}
void solve()
{
	int res = 1;
	for (int i = 0; i<n; i++) {
		total = 0;
		for (int j = 0; j<n; j++) {
			if (i == j) continue;
			double dist = Dis(point[i], point[j]);
			if (dist>2.0 * R) continue;
			double base = God(point[i], point[j]);
			double extra = acos((dist / 2.0) / R); //计算差角
			angle[total].data = base - extra; // in
			angle[total++].is = 1;
			angle[total].data = base + extra; // out
			angle[total++].is = -1;
		}
		if (total <= res) continue;
		sort(angle, angle + total);
		int tmp = 1;
		for (int j = 0; j<total; j++) {
			tmp += angle[j].is;
			res = max(res, tmp);
		}
	}
	printf("%d\n", res);
}
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &R);
	for (int i = 0; i<n; i++) {
		scanf("%lf %lf", &point[i].x, &point[i].y);
	}
	solve();
	return 0;
}

本代码提交AC,用时1345MS。
平时几乎没做过计算几何的题目,发现好难呀。

hihoCoder 1506-投掷硬币

hihoCoder 1506-投掷硬币

#1506 : 投掷硬币

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一枚神奇的硬币。已知第i次投掷这枚硬币时,正面向上的概率是Pi
现在小Hi想知道如果总共投掷N次,其中恰好M次正面向上的概率是多少。

输入

第一行包含两个整数N和M。
第二行包含N个实数P1, P2, ... PN
对于30%的数据,1 <= N <= 20
对于100%的数据,1 <= N <= 1000, 0 <= M <= N, 0 <= Pi <= 1

输出

输出一行一个实数表示恰好M次正面向上的概率。注意行末需要包含一个换行符'\n'。
输出与标准答案误差在0.001以内都被视为正确。

样例输入
2 1
0.5 0.5
样例输出
0.500000

某枚硬币在第i次投掷时,正面向上的概率为Pi,现在投掷N次,问恰好有M次正面向上的概率是多少。
这一题可以看成有N枚硬币,编号1~N,第i枚硬币正面向上的概率为Pi,把所有硬币一起抛向空中,问落地之后出现M枚正面向上的概率。
我一开始是这么做的,每一枚硬币都有可能正面向上或者反面向上,所以枚举所有2^N种情况,累加所有出现M次正面向上的概率。其实就是DFS,代码如下:

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
double ans = 0;
int n, m;
void dfs(const vector<double>& probs, double curprob, int step, int up) {
	if (up == m) {
		double oneans = curprob;
		for (int i = step; i < n; ++i)oneans *= (1 - probs[i]);
		ans += oneans;
		return;
	}
	if (step < n) {
		dfs(probs, curprob*probs[step], step + 1, up + 1);
		dfs(probs, curprob*(1 - probs[step]), step + 1, up);
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	vector<double> probs(n, 0);
	for (int i = 0; i < n; ++i) scanf("%lf", &probs[i]);
	dfs(probs, 1, 0, 0);
	printf("%lf\n", ans);
	return 0;
}

不出所料,本代码提交TLE,只能过30%的数据。
其实每一枚硬币都有正面向上或者反面向上的选择,马上想到背包问题,对于每个商品有选或者不选这两种情况,所以本题实际上也是换了个马甲的背包问题。
令dp[i][j]表示前i枚硬币出现j枚正面向上的概率。那么对于第i枚硬币,有两种选择,如果第i枚硬币正面向上,则前i-1枚硬币只能有j-1枚正面向上,即dp[i][j]+=dp[i-1][j-1]*probs[i]。如果第i枚硬币反面向上,则前i-1枚硬币需要有j枚正面向上,所以dp[i][j-1]+=dp[i-1][j-1]*(1-probs[i])。最终返回dp[n][m]。
代码如下:

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
int main() {
	//freopen("input.txt", "r", stdin);
	int n, m;
	scanf("%d %d", &n, &m);
	vector<double> probs(n + 1, 0);
	for (int i = 1; i <= n; ++i)scanf("%lf", &probs[i]);
	vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
	dp[0][0] = 1.0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) { //现在有i枚硬币,所以正面向上的个数j不超过i
			dp[i][j] += dp[i - 1][j - 1] * probs[i];  // head
			dp[i][j - 1] += dp[i - 1][j - 1] * (1 - probs[i]); // tail
		}
	}
	printf("%lf\n", dp[n][m]);
	return 0;
}

本代码提交AC,用时48MS。