对抗赛
【问题描述】
程序设计对抗赛设有N（0
例如N=5，S1，S2，S3...,Sn分别为1,3,5,8,9
则可分为{1,3,9}与{5,8}，仅有一种分法；
例如N=7，S1，S2，S3...,Sn分别为1,2,3,4,5,6,7
则可分为：
{1,6,7}与{2,3,4,5}
{2,5,7}与{1,3,4,5}
{3,4,7}与{1,2,5,6}
{1,2,4,7}与{3,5,6}
有4种分法。
【输入格式】
N
S1，S2，S3，...,Sn.
【输出格式】
共有多少种分法，无解则输出0；
【输入样例】
7
1 2 3 4 5 6 7
【输出样例】
4
【解题思路】
计数问题，标准的递推；
f[i][j]表示把前i个数分成两份，每份的和是j的方案数；
f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
一个极类似于背包的方程；
其实就相当于从这么多数中选出一些数让他们的和等于总和的一半；
最后的结果是要/2的，因为递推的时候把比如{1,3,9}与{5,8}和{5,8}与{1,3,9}当做了两种情况，也就是{1,3,5}选了一次，{5,8}选了一次；
【代码】
【dp|对抗赛 解题报告】
#include
#include
#include
using namespace std;
int n,i,j,m;
long long a[55],f[55][5005];
int main()
{
freopen("compete.in","r",stdin);
freopen("compete.out","w",stdout);
scanf("%d",&n);
for (i=1;
i<=n;
++i)
{
scanf("%d",&a[i]);
m+=a[i];
}
if (m%2!=0)
{
printf("0");
return 0;
}
f[0][0]=1;
for (i=1;
i<=n;
++i)
for (j=0;
j<=m/2;
++j)
{
f[i][j]=f[i-1][j];
if (j-a[i]>=0) f[i][j]+=f[i-1][j-a[i]];
}
cout< 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- 2019 GDUT Rating Contest #II 这是群题解，七篇！！！
- # 2019 GDUT Rating Contest #I H. Mixing Milk
- # 2019 GDUT Rating Contest #I A. The Bucket List
- # 2019 GDUT Rating Contest #I G. Back and Forth