首页 > 代码库 > [JZOJ P1271] [DP]集合求和
[JZOJ P1271] [DP]集合求和
@kaike
传送门
就这么简单的题目，我交了四回？
让你用 1-n 个数看是否能组成等式
可以看出 1-n 明显是一个等差数列 恩
数列题刷的都要吐了不过不难
由求和公式Sn=n*（n+1)/2
组成等式 左边=右边=Sn/2
先判断是否有解
1 s=n*(n+1);2 if(s%4!=0)3 {4 cout<<0<<endl;5 return 0;6 }
设边界f[0]=1
如背包问题
我知道这是一个很恶劣的词语，但是具体我还没有悟出来
f[j]=f[j]+f[j-i];
这一次的分法就等于这一次j比i多出来的数的分法加上原来i的分法
注意long long ！！！
1 #include<iostream> 2 using namespace std; 3 long long n,f[10000100],s; 4 int main() 5 { 6 cin>>n; 7 s=n*(n+1); 8 if(s%4!=0) 9 {10 cout<<0<<endl;11 return 0;12 }13 s/=4;14 f[0]=1;15 for(int i=1;i<=n;i++)16 for(int j=s;j>=i;j--)17 f[j]+=f[j-i];18 cout<<f[s]/2<<endl;19 return 0;20 }
[JZOJ P1271] [DP]集合求和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。