Description
给出一个N行3列非负整数矩阵的各行各列之和,统计有多少个矩阵满足此条件。输出答案模10^17的值。
Input
第一行包含四个正整数N,c1, c2, c3,即行数与三列之和。第二行包含N个正整数,即各行三个数之和。每行每列之和均不超过125。
Output
仅一个数,满足条件的矩阵个数模10^17的值。
Sample Input
3 2 3 4
1 2 6
Sample Output
17
Hint
1<=N<=200
思路:考虑dp
设 表示到第 行时, 第一列的和为 ,第二列的和为 ,第三列的和为
由于第三列的和可以通过第一二列推得,故只需设
容易想到状态转移方程 其中
观察可发现只出现 和 ,故可以用滚动数组进行优化 (虽然我并没有那么做)
#include <bits/stdc++.h>
using namespace std;
int N , c1 , c2 , c3 , a[201];
long long f[201][201][201]={0};
int main() {
cin >> N >> c1 >> c2 >> c3;
for (register int i=1; i<=N; i++) cin >> a[i];
f[0][0][0]=1;
for (register int i=1; i<=N; i++) {
for (register int j=0; j<=c1; j++) {
for (register int k=0; k<=c2; k++) {
for (register int x=0; x<=a[i] , x+j<=c1; x++) {
for (register int y=0; y<=a[i] , y+k<=c2 , x+y<=a[i]; y++) {
f[i][j+x][k+y]=(f[i-1][j][k]+f[i][j+x][k+y])%100000000000000000;
}}}}}
cout << f[N][c1][c2] << endl;
return 0;
}
原文链接: https://www.cnblogs.com/i-willbe233/p/13519895.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/368869
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!