思路

令所有人物战力之和为 $sum$ 。即在 $n$ 个人物中，选择 $x$ 个人物，满足 $1\leq x < n$ 且这 $x$ 人的战力之和为 $sum$ 的一半。

定义 $f[i][j]$ 表示只考虑前 $i$ 个人物，选择的人物的战力之和恰好为 $j$ 的情况是否存在。如果 $f[i][j] = 1$ 表示存在，如果 $f[i][j] = 0$ 表示不存在。

那么状态转移为：

P1440.2023.08.11-第二题-塔子哥的新游戏

1000ms

Difficulty: 6

算法与标签>动态规划

塔子哥超级喜欢玩游戏，最近又开发了一款新的游戏。

游戏公平是塔子哥一直追求的，所以他想让你帮忙测试下这个游戏是否公平。塔子哥会给出游戏中每个人物的战力 $a_i$ ，公平的定义是可以将所有人物分成两组，每组都有至少一个人物，且两组的人物战力之和相等。

请你帮忙测试下是否有一种划分方案使得游戏公平。

一行，首先输入一个正整数 $n$ 表示游戏人物个数，接下来 $n$ 正整数表示 $n$ 个游戏人物的战力。

$1\leq n\leq 1000, \sum\limits_{i=1}^n a_i\leq 20000$

如果有一种方案使得游戏公平，输出1，否则输出0。

输入

7 9 8 2 4 3 5 3

输出

编辑器加载中…

输入

预期输出（选填）