列表

详情

NC236615. 牛牛的骑士游戏

描述

牛牛在玩一款游戏。
牛牛有 n 个骑士，第 i 个骑士具有 s_i 个技能第 j 个技能的伤害是 需要的能量是 。
牛牛想要打败大魔王，大魔王的血量是 m，只要牛牛的骑士对大魔王造成的伤害和大于等于（当所有骑士攻击结束后才结算伤害，不存在魔王中途死亡的情况） m 那就认为牛牛战胜了大魔王。
在一个方案中，牛牛的每一个骑士都可以使用任意个技能（可以不出技能，但是每个技能最多只能被使用一次）。
现在牛牛想要知道自己有多少种击败魔王的方案，特别的，由于牛牛待会还要去挑战巨龙，所以两种方案不同当且仅当所有骑士攻击完魔王后，至少存在一个骑士在两种方案中使用的能量总和不同。
你能告诉牛牛它有多少种不同的方案来击败魔王吗？由于方案数可能特别大，所以你只需要输出方案数模 998244353 之后的结果即可。

输入描述

输入第一行两个整数代表 n,m 。
接下来共 n 行，每行描述了一个骑士的技能数和技能伤害以及技能需要消耗的能量。
第 i 行首先输入一个数代表 s_i 接下来输入  个数，前 s_i 个数代表这个骑士每个技能的伤害，后 s_i 个数代表这个骑士每个技能的能量消耗，这里的伤害和能量消耗是一一对应的。
保证：

输出描述

输出一行一个整数代表牛牛不同的击败魔王的方案数模 998244353 之后的结果。 

示例1

输入: 

1 2
2 2 3 2 2

输出: 

2

说明:

共 4 种方案：
    1.骑士出第一个技能；（能量消耗为 2，伤害为 2）
    2.骑士出第二个技能；（能量消耗为 2，伤害为 3）
    3.骑士出第一个和第二个技能；（能量消耗为 4，伤害为 5）
    4.骑士不使用任何一个技能；（能量消耗为 0，伤害为 0）
依据题意能够击败魔王的方案是：1，2，3；
但是由于方案 1，2 的能量消耗量是相同的，所以看作是同一种方案，所以不同的方案数为：2。

示例2

输入: 

3 4
2 1 2 1 2
2 2 1 2 2
1 1 1

输出: 

13

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 68ms, 内存消耗: 472K, 提交时间: 2023-01-11 20:34:21 

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lod long double
#define FILE(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)
using namespace std;
const int N=3e3+5,mod=998244353;
int n,m,a[N],dp[N],maxn[N],nxt[N];
bool flag[N];
signed main()
{
	scanf("%d%d",&n,&m);
	dp[0]=1;
	while(n--)
	{
		memset(flag,0,sizeof flag);
		memset(maxn,0,sizeof maxn);
		flag[0]=1;
		int cnt;
		scanf("%d",&cnt);
		for(int i=1;i<=cnt;++i)
			scanf("%d",a+i);
		for(int i=1;i<=cnt;++i)
		{
			int b;
			scanf("%d",&b);
			for(int j=3000;j>=b;--j)
			{
				if(flag[j-b])
				{
					flag[j]=1;
					maxn[j]=max(maxn[j],maxn[j-b]+a[i]);
				}
			}
		}
		memset(nxt,0,sizeof nxt);
		for(int i=0;i<=3000;++i)
		{
			if(flag[i])
			{
				for(int j=0;j<=m;++j)
					nxt[min(j+maxn[i],m)]=(nxt[min(j+maxn[i],m)]+dp[j])%mod;
			}
		}
		memcpy(dp,nxt,sizeof nxt);
	}
	printf("%d",dp[m]);
	return 0;
}

C++ 解法, 执行用时: 130ms, 内存消耗: 80640K, 提交时间: 2022-07-20 21:20:10 

#include<bits/stdc++.h>
#define mod 998244353
#define N 10001
using namespace std;
int a[N],b[N],g[N];
long long f[N][N];
int main()
{
	int i,j,k,n,m,s,x;
	long long sum=0;
	cin>>n>>m; f[0][0]=1;
	for (i=1;i<=n;i++){
		cin>>s;
		for (j=1;j<=s;j++) cin>>a[j];
		for (j=1;j<=s;j++) cin>>b[j],sum+=b[j];
		for (j=1;j<=3000;j++) g[j]=-1000000000;
		g[0]=0;
		for (j=1;j<=s;j++)
			for (k=sum;k>=b[j];k--)
				g[k]=max(g[k],g[k-b[j]]+a[j]);
		for (j=0;j<=sum;j++){
			if (g[j]<0) continue;
			for (k=0;k<=m;k++){
				x=min(m,k+g[j]); f[i][x]=(f[i][x]+f[i-1][k])%mod;
			}
		}
	}
	cout<<f[n][m];
	return 0;
}

上一题

© 2024 nowcoder.com