线性DP求调
查看原帖
线性DP求调
815957
apple_vinegar楼主2024/10/4 10:43
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=10;
int a[N];

inline int read(){
	int a=1,b=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') a=-a;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		b=(b<<1)+(b<<3)+(ch^48);
		ch=getchar();
	}
	return a*b;
}

signed main(){
	while(int k=read()){
		for(int i=1;i<=5;i++) a[i]=0;
		for(int i=1;i<=k;i++) a[i]=read();
		int dp[a[1]+1][a[2]+1][a[3]+1][a[4]+1][a[5]+1];
		memset(dp,0,sizeof dp);
		dp[0][0][0][0][0]=1;
		for(int i=0;i<=a[1];i++){
			for(int j=0;j<=a[2];j++){
				for(int l=0;l<=a[3];l++){
					for(int m=0;m<=a[4];m++){
						for(int n=0;n<=a[5];n++){
							if(i<a[1]) dp[i+1][j][l][m][n]+=dp[i][j][l][m][n];
							if(j<a[2]&&j<i) dp[i][j+1][l][m][n]+=dp[i][j][l][m][n];
							if(l<a[3]&&l<j) dp[i][j][l+1][m][n]+=dp[i][j][l][m][n];
							if(m<a[4]&&m<l) dp[i][j][l][m+1][n]+=dp[i][j][l][m][n];
							if(n<a[5]&&n<m) dp[i][j][l][m][n+1]+=dp[i][j][l][m][n];
						}
					}
				}
			}
		}
		printf("%lld\n",dp[a[1]][a[2]][a[3]][a[4]][a[5]]);
	}
	return 0;
}
2024/10/4 10:43
加载中...