3.采访（interview）

题目描述

你是一名记者，现在要求你去采访n 个国家的领导人。采访每一个国家的领导人需要消耗你的时间为t[i]，但你可以收获价值为v[i]的信息，然后就能写成报道……
然而尴尬的是，有一些国家之间的关系属于敌对关系，因此如果一个国家的领导人知道你采访了他的敌对国家领导人，那么他就会拒绝你的采访。总之，你采访的国家中，任意选出一对国家都不能构成敌对关系，你才能够完成你的采访，否则某些部分就要落空。
你的Boss他给了你一个时间限制T，如果你在时间限制内没有完成采访任务，你就会被炒鱿鱼。当然，他希望你在时间限制T 内完成的采访累计起来的价值总和最大。

输入

第一行有三个数，第一个数为时间限制T，第二个数为国家数量n，第三个数为国家之间的敌对组数m。
接下来n 行，每行两个数，第一个数为t[i]，第二个数为v[i]。
接下来m 行，每行有m[i]+1 个数，首先输入m[i]，表示这一组中一共有多少国家是敌对关系，之后输入m[i]个数，表示这m[i]个国家两两之间为敌对关系（一组敌对关系的国家中，每两个国家都构成敌对关系，比如这一组是1，3，4，那么1 和3，1 和4，3 和4 都构成敌对关系），若m[i] = 1，那么这个国家与其他国家都不构成敌对关系。

输出

一个整数，表示最大价值V。

样例输入

10 5 2
5 10
7 9
6 3
1 13
8 1
3 1 3 4
2 2 5

样例输出

22

数据范围限制

60%的数据：m=1；
100%的数据：0≤T≤50000，0≤n≤500，1≤m≤10，n=∑m[i]，即m[1]+m[2]+…=n，且敌对关系中每个国家编号只会出现一次。

正解
分组背包模板
AC代码

#include<cstdio>
using namespace std;
int t,n,m,o,a,w[505],v[505],f[15][50005];
int main()
{
   
	freopen("interview.in","r",stdin);
	freopen("interview.out","w",stdout);
	cin>>t>>n>>m; 
	for(int i=1;i<=n;i++)
	 cin>>w[i]>>v[i];
	for(int i=1;i<=m;i++)//分组背包模板
	{
   
		cin>>o;
		for(int j=0;j<=t;j++)f[i][j]=f[i-1][j];
		for(int j=1;j<=o;j++)
		{
   
			cin>>a;
			for(int k=t;k>=w[a];k--)
			 f[i][k]=max(f[i][k],f[i-1][k-w[a]]+v[a]);
		}
	}
	cout<<f[m][t]; 
	return 0;
}

下面附本次比赛的其它题目

2020.03.11模拟赛15（第一题）
2020.03.11模拟赛15（第二题）
2020.03.11模拟赛15（第三题）
2020.03.11模拟赛15（第四题）
2020.03.11模拟赛15（总结）

谢谢