专栏文章

P1464 Function 题解

P1464题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minr45ef
此快照首次捕获于
2025/12/02 06:59
3 个月前
此快照最后确认于
2025/12/02 06:59
3 个月前
查看原文

P1464 Function 题解

需要用到记忆化搜索
CPP
#include <bits/stdc++.h>//模拟 + 记忆化搜索 
using namespace std;
int dp[30][30][30];
long long w(long long a,long long b,long long c){
	if(a <= 0 || b <= 0 || c <= 0) return 1;
	if(a > 20 || b > 20 || c > 20) return w(20,20,20);//两个特判 
	if(a < b && b < c){//情况1  挨个录 
		if(!dp[a][b][c-1]) dp[a][b][c-1] = w(a,b,c-1);
		if(!dp[a][b-1][c-1]) dp[a][b-1][c-1] = w(a,b-1,c-1);
		if(!dp[a][b-1][c]) dp[a][b-1][c] = w(a,b-1,c);
		dp[a][b][c] = dp[a][b][c-1]+dp[a][b-1][c-1]-dp[a][b-1][c];
	}else{//情况二 挨个录 
		if(!dp[a-1][b][c]) dp[a-1][b][c] = w(a-1,b,c);
		if(!dp[a-1][b-1][c]) dp[a-1][b-1][c] = w(a-1,b-1,c);
		if(!dp[a-1][b][c-1]) dp[a-1][b][c-1] = w(a-1,b,c-1);
		if(!dp[a-1][b-1][c-1]) dp[a-1][b-1][c-1] = w(a-1,b-1,c-1);
		dp[a][b][c] = dp[a-1][b][c] + dp[a-1][b][c-1] + dp[a-1][b-1][c] - dp[a-1][b-1][c-1];
	}
	return dp[a][b][c]; 
}
int main(){
	long long a,b,c;
	while(scanf("%lld%lld%lld",&a,&b,&c)){
		if(a == -1 && b == -1 && c == -1) return 0;
		printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
	}
	return 0;
}  

评论

0 条评论,欢迎与作者交流。

正在加载评论...