游客 注册 | 登录
中文 | En

2018 - 大富翁

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

大富翁的游戏应该都不陌生，就是掷个骰子，然后根据点数往前走，花钱盖房子，然后其他人走到别人的房子要交钱，最后谁没有破产谁就获胜了。
现在有一条路，长度为n，标记为0~n-1。你控制的人物初始位置在x，然后每次行动抽一张牌，根据上面的点数进行移动，你可以选择向前移动或者向后移动，现在想知道经过m次移动后最大位置可以移动到哪里，当然控制的人物不能走出这条路外面。

题目输入

第一行输入一个数T，表示测试数据的个数，接下来输入n，m，x，表示路的长度、操作的次数和初始位置。下一行输入m个数，表示m次抽牌的点数，当然这些牌操作时候顺序不能打乱。
数据范围：
0<n,m,x<=1000
0<=牌的点数<=n

题目输出

对于每个测试数据输出一个数，表示经过m次移动之后移动到的最大位置，如果移动不了，输出-1.

输入/输出样例

输入格式

2
11 3 5
5 3 7
20 4 8
15 2 9 10

输出格式

10
-1

C++解答

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
#define maxn 1010
int dp[2][maxn];
int now;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,x;
        scanf("%d%d%d",&n,&m,&x);
      	now=0;
      	memset(dp[0],0,sizeof dp[0]);
        dp[0][x]=1;
        for(int i=0;i<m;i++){
            scanf("%d",&x);
          	now^=1;memset(dp[now],0,sizeof dp[now]);
          	for(int j=0;j<n;j++){
            	if(dp[now^1][j]){
       				if(j+x<n) dp[now][j+x]=1;
                  	if(j-x>=0) dp[now][j-x]=1;
                }
            }
        }
      	int ans=-1;
      	for(int i=n-1;i>=0;i--){
        	if(dp[now][i]){
            	ans=i;break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
请先登陆