小欧的卡牌
题目描述
小欧有 n 张卡牌,第 i 张卡牌的正面写了个数字 ai,背面写了个数字 bi。小欧对于每张卡牌可以选择一面向上,她希望最终向上的数字之和为 3 的倍数。你能告诉小欧有多少方案吗?由于答案过大,请对 10 ^ 9 + 7 取模.
输入描述
第一行输入一个正整数 n,代表卡牌数量。
接下来的 n 行,每行输入两个正整数 ai 和 bi,代表第 i 张卡牌的正面和背面的数字. 1 <= n <= 10^5 1 <= ai,bi <= 10^9
输出描述
一个整数,代表方案数对 10^9 + 7 取模的值
输入示例
3 1 2 2 3 3 2
输出示例
3
思路:
看起来比较唬人的一道题目,但是使用动态规划很容易解决
首先针对输入卡牌的值我们可以全部进行对3取模处理,因为实际上每个数对3取模后剩的数才会影响到最终和是否能整除3
然后采用动态规划。
动态规划三部曲:
dp数组的设计与具体含义:dp[i][j]
代表从第一张到第i张卡牌数之和等于j的情况数
dp数组状态转移方程:dp[i][j] = dp[i-1][(j-card[i][0]+3)%3]+dp[i-1][(j-card[i][1]+3)%3] j属于{0,1,2}
(card[i] [0]表示第i张正面的数,card[i] [1]表示第i张反面的数)
dp数组初始化: dp[0][0]=1
,即第0张牌和为0的情况数为1
滚动数组优化:
由于i层dp数组的状态完全依赖于i-1层,与i-2、i-3等均无关,所以此处使用2层即可,具体看代码实现
import java.lang.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] card = new int[n][2]; for(int i = 0;i<n;i++){ card[i][0] = in.nextInt()%3; card[i][1] = in.nextInt()%3; } int[][] dp = new int[2][3]; dp[0][0] = 1; for(int i = 0;i<n;i++){ for(int j = 0;j<3;j++){ dp[1][j] = (dp[0][(j-card[i][0]+3)%3] + dp[0][(j-card[i][1]+3)%3])%((int)1e9+7); } dp[0] = Arrays.copyOf(dp[1],3); } System.out.println(dp[1][0]); } }