p1149火柴棒等式，dp打表
主要是怎么求每个数的火柴数
设一个数字火柴数dp【i】，dp【i】=dp【i/10】+dp【i%10】
dp打表代码（时间最佳）
#include <bits/stdc++.h>
using namespace std;
int n,ans;
int num[2005]={6,2,5,5,4,5,6,3,7,6};
int main(int argc, char** argv) {
cin>>n;
n-=4;
for(int i=10;i<=2000;i++){
num[i]=num[i/10]+num[i%10];
}
for(int i=0;i<=1000;i++){
for(int j=0;j<=1000;j++){
if(num[i]+num[j]+num[i+j]==n) ans++;
}
}
cout<<ans<<endl;
return 0;
} 也可用while取每个位数来求（和上基本持平，大数据时较差）
#include <bits/stdc++.h>
using namespace std;
int n,ans;
int alph[10]={6,2,5,5,4,5,6,3,7,6};
int num[2005]={6};//0在初始化时不好处理
int main(int argc, char** argv) {
cin>>n;
n-=4;
for(int i=1;i<=2000;i++){
int j=i;
while(j){
num[i]+=alph[j%10];
j/=10;
}
}
for(int i=0;i<=1000;i++){
for(int j=0;j<=1000;j++){
if(num[i]+num[j]+num[i+j]==n) ans++;
}
}
cout<<ans<<endl;
return 0;
} 临时递归（最差的效率，耗时是上10倍以上）
#include <bits/stdc++.h>
using namespace std;
int n,ans;
int num[2005]={6,2,5,5,4,5,6,3,7,6};
int count(int x){
int ans=0;
if(x==0) return 6;
while(x){
ans+=num[x%10];
x/=10;
}
return ans;
}
int main(int argc, char** argv) {
cin>>n;
n-=4;
for(int i=0;i<=1000;i++){
for(int j=0;j<=1000;j++){
if(count(i)+count(j)+count(i+j)==n) ans++;
}
}
cout<<ans<<endl;
return 0;
} 
投递蔚来等公司10个岗位 >
查看3道真题和解析