人生重开模拟器

NC229636. 人生重开模拟器

描述

这垃圾人生一秒也不想呆了，小咸鱼最近迷恋上了"人生重开模拟器"，这是一款文字解密玩法的游戏。

玩家需要在开局从n个天赋中选择出x个天赋，每个天赋都可获得对应的属性点，所选天赋的属性点之和为s，s个属性点可以自由分配给m个属性中，给第i个属性分配j个属性点时，可获得P(i,j)点能力值，现在小咸鱼想知道他能最多得到多少点能力值。

输入描述

本题为多组测试数据，第一行输入一个整数T( $1\le T\le 100$ )，表示测试数据的组数。

对于每组数据，第一行输入三个整数n,x,m( $1\le x\le 10$ ； $1\le n,m\le 100$ )，代表玩家需要从n个天赋中选出x个天赋,所获得属性点分配给m个属性。

第二行依次输入n个正整数 $v_1$ ， $v_2$ ，... ， $v_n$ （ $1\le v_i\le 10$ ）,代表每个天赋对应的属性点,所选天赋的属性点之和记为s。

接下来输入m行，每行输入s个正整数 $c_1$ ， $c_2$ ，... ， $c_s$ （ $1\le c_i\le 1000$ ）,代表给当前属性加i个属性点可获得 $c_i$ 点能力值。

输出描述

对于每组测试数据，一行输出一个整数代表小咸鱼最多得到的能力值。如果给某属性加的属性点为0，那通过此属性所得到能力值为0。

示例1

输入:

1
10 3 2
1 2 3 1 1 2 2 1 0 1
1 1 2 3 1 1 2
1 3 2 1 2 2 2

输出:

原站题解

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

C++ 解法, 执行用时: 118ms, 内存消耗: 876K, 提交时间: 2021-11-07 13:50:06

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int T,n,m,x,s,v[150],c[150][1005],f[150][150],ans;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&x,&m);
		for(int i=1;i<=n;i++) scanf("%d",&v[i]);
		sort(v+1,v+n+1);s=ans=0;
		for(int i=n;i>=n-x+1;i--) s+=v[i];
		for(int i=1;i<=m;i++)
			for(int j=1;j<=s;j++)
				scanf("%d",&c[i][j]),f[i][j]=0;
		for(int k=1;k<=m;k++)
			for(int i=0;i<=s;i++)
				for(int j=0;j<=i;j++)
					f[k][i]=max(f[k][i],f[k-1][j]+c[k][i-j]);
		for(int i=0;i<=s;i++) ans=max(ans,f[m][i]);
		printf("%d\n",ans);
	}
	return 0;
}

上一题

下一题

详情