1293 球与切换器(dp)

2017-07-12 129点热度 0人点赞
题目来源: Codility
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题

1293 球与切换器(dp) 收藏

1293 球与切换器(dp) 关注
有N行M列的正方形盒子。每个盒子有三种状态0, -1, +1。球从盒子上边或左边进入盒子,从下边或右边离开盒子。规则:
如果盒子的模式是-1,则进入它的球从下面出去。(方向变为向下)
如果盒子的模式是+1,则进入它的球从右面出去。 (反向变为向右)
如果盒子的模式是0, 则进入它的球方向不变。从上面进入的,从下面出去,从左面进入的,从右面出去。
1293 球与切换器(dp)
球离开一个盒子,这个盒子的模式切换为相反数。已知,每个盒子的状态,扔k个球,它们都从左上角那个盒子的上面进入(方向向下),问最终有几个球从右下角的盒子的下边出去。
(可以理解维球一个一个放,等待的时间足够长,不会有两个球同时进入一个盒子的情形)本题由Javaman翻译。
Input
第1行:包括3个数M, N, K中间用空格分隔,M,N 为盒子的宽度和高度,K为球的数量(1 <= M, N <= 1000, 1 <= K <= 10^18)。
第2 - N + 1行:每行M个数(-1, 0 或 1),表示对应的模式。
Output
输出1个数,对应最终有有多少个球从右下角的盒子的下边出去。
Input示例
3 2 4
-1 0 -1
1 0 0
Output示例

1

//非常的巧妙的递推, dp[i][j][0]表示到达i,j向下并且向下的个数,dp[i][j][1]表示向右 
#include
int n,m;
long long k;
long long dp[1001][1001][2];
int main()
{
//	freopen("1.txt","r",stdin);
	int t;
	scanf("%d%d%lld",&n,&m,&k);
	dp[0][0][0]=k;
	for(int i=0;i

未经允许不得转载!1293 球与切换器(dp)

本文地址:https://ai.52learn.online/522

站长邮箱:ai52learn@foxmail.com