2025年K13324 科丁乐战旗

科技前沿 • 2025-03-14 23:41 • 阅读 37

大家好，我是讯享网，很高兴认识大家。

题目描述

小丁和小乐正在玩科丁乐新推出的战旗卡牌游戏，该游戏中共有N张战旗卡牌，每张战旗卡牌都有一个数值，表示该卡牌的战斗力。这n张战旗卡牌中并不是所有的牌都能使用，必须得满足裁判规定的条件，例如本局游戏，裁判就规定只能使用数值为素数的战旗卡牌。小丁和小乐希望将这N张卡牌中所有的素数卡牌分成总和相等的两份（每份中的战旗卡牌数量不一定相等）。请帮助小丁和小乐计算，是否可以将所有的素数卡牌分成总和相等的两份，如果可以输出YES，否则输出NO。

输入格式

第1行：一个正数T，代表测试数据的组数

每组数据第1行：一个正数N，代表卡牌的数量

每组数据第2行：N个空格分隔的正整数，第i个数代表战旗卡牌i上的分数si 。

输出格式

讯享网

每组测试数据输出一行：如果可以将所有的素数卡牌分成总和相等的两份则输出YES,否则输出NO

输入输出样例

输入样例1：

2 3 1 2 3 8 1 2 3 5 6 7 8 11

讯享网

输出样例1：

讯享网NO YES

说明

【数据范围】：

对于100%的数据，1≤T≤10，2≤N≤100，1≤si≤100

【耗时限制】1000ms 【内存限制】128MB

// //Created by Carlgood. // //Note:This program is written in version DEV-C++ 5.11. //Subject source:"hppt://oj.codingle.cn" # include <iostream> # include<cmath> # include<string> # include<cstring> # include<cstdio> # include<algorithm> # include<sstream> # define This_program_is_written_by_Carlgood_Programming_Studio  using namespace std; int dp[102][5002]; int a[102]; bool is_prime(const int &x) { if(x<2) { return false; } for(int i=2;i*i<=x;i++) { if(x%i==0) return false; } return true; } int main() { int rbt; cin>>rbt; while(rbt--) { bool flag=false; int n,sum=0,cnt=1,x; cin>>n; for(int i=1;i<=n;i++) { cin>>x; if(is_prime(x)) { a[++cnt]=x; sum+=x; } } if(sum%2!=0) { cout<<"NO\n"; continue; } sum/=2; for(int i=1;i<=cnt;i++) { for(int j=1;j<=sum;j++) { if(a[i]>j) { dp[i][j]=dp[i-1][j]; } else if(a[i]==j) { dp[i][j]=dp[i-1][j]+1; } else { dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]; } if(dp[i][j]!=0) dp[i][j]=1; } } if(dp[cnt][sum]!=0) cout<<"YES\n"; else cout<<"NO\n"; } return 0; }

2025年K13324 科丁乐战旗

输入样例1：

输出样例1：

相关推荐