P1149 [NOIP2008 提高组] 火柴棒等式
[NOIP2008 提高组] 火柴棒等式
题目描述
给你 n n n 根火柴棍,你可以拼出多少个形如 A + B = C A+B=C A+B=C 的等式?等式中的 A A A、 B B B、 C C C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 0 0 0)。用火柴棍拼数字 0 ∼ 9 0\sim9 0∼9 的拼法如图所示:
注意:
- 加号与等号各自需要两根火柴棍;
- 如果 A ≠ B A\neq B A=B,则 A + B = C A+B=C A+B=C 与 B + A = C B+A=C B+A=C 视为不同的等式( A , B , C ≥ 0 A,B,C\geq0 A,B,C≥0);
- n n n 根火柴棍必须全部用上。
输入格式
一个整数 n ( 1 ≤ n ≤ 24 ) n(1 \leq n\leq 24) n(1≤n≤24)。
输出格式
一个整数,能拼成的不同等式的数目。
样例 #1
样例输入 #1
14
样例输出 #1
2
样例 #2
样例输入 #2
18
样例输出 #2
9
提示
【输入输出样例 1 解释】
2 2 2 个等式为 0 + 1 = 1 0+1=1 0+1=1 和 1 + 0 = 1 1+0=1 1+0=1。
【输入输出样例 2 解释】
9 9 9 个等式为
0 + 4 = 4 0+4=4 0+4=4、 0 + 11 = 11 0+11=11 0+11=11、 1 + 10 = 11 1+10=11 1+10=11、 2 + 2 = 4 2+2=4 2+2=4、 2 + 7 = 9 2+7=9 2+7=9、 4 + 0 = 4 4+0=4 4+0=4、 7 + 2 = 9 7+2=9 7+2=9、 10 + 1 = 11 10+1=11 10+1=11、 11 + 0 = 11 11+0=11 11+0=11。
noip2008 提高第二题
没有任何优化的代码:
#include<iostream>
using namespace std;
const int N=10010;
int n;
int arr[N];
int res=0;
int nums[10010]={6,2,5,5,4,5,6,3,7,6};//存数字所需要的火柴棍
int col(int x){
if(nums[x]>0) return nums[x];
else{
int sumfire=0;
while(x){
sumfire+=nums[x%10];
x/=10;
}
return sumfire;
}
}
void dfs(int x,int sum){
if(x>3){
if(arr[1]+arr[2]==arr[3]&&sum==n){
res++;
}
return ;
}
for(int i=0;i<=1000;i++){
arr[x]=i;
dfs(x+1,sum+col(i));
arr[x]=0;
}
}
int main(){
cin>>n;
n-=4;
dfs(1,0);
cout<<res;
return 0;
}
剪枝后代码:
#include<iostream>
using namespace std;
const int N=10010;
int n;
int arr[N];
int res=0;
int nums[10010]={6,2,5,5,4,5,6,3,7,6};//存数字所需要的火柴棍
int col(int x){
if(nums[x]>0) return nums[x];
else{
int sumfire=0;
while(x){
sumfire+=nums[x%10];
x/=10;
}
return sumfire;
}
}
void dfs(int x,int sum){
if(sum>n) return ;
if(x>3){
if(arr[1]+arr[2]==arr[3]&&sum==n){
res++;
}
return ;
}
for(int i=0;i<=1000;i++){
arr[x]=i;
dfs(x+1,sum+col(i));
arr[x]=0;
}
}
int main(){
cin>>n;
n-=4;
dfs(1,0);
cout<<res;
return 0;
}
用递推优化后的代码:
#include<iostream>
using namespace std;
const int N=10010;
int n;
int arr[N];
int res=0;
int nums[10010]={6,2,5,5,4,5,6,3,7,6};//存数字所需要的火柴棍
void dfs(int x,int sum){
if(sum>n) return ;
if(x>3){
if(arr[1]+arr[2]==arr[3]&&sum==n){
res++;
}
return ;
}
for(int i=0;i<=1000;i++){
arr[x]=i;
dfs(x+1,sum+nums[i]);
arr[x]=0;
}
}
int main(){
cin>>n;
n-=4;
for(int i=10;i<=1000;i++){//递推出10~1000需要用到的火柴棍,可以直接使用,不需要一次一次的算
nums[i]=nums[i%10]+nums[i/10];
}
dfs(1,0);
cout<<res;
return 0;
}
原文地址:https://blog.csdn.net/2301_80662593/article/details/140507107
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!