社区讨论
DP做法,请问为什么错了
P11229[CSP-J 2024] 小木棍参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhj94wte
- 此快照首次捕获于
- 2025/11/03 22:45 4 个月前
- 此快照最后确认于
- 2025/11/03 22:45 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N];//木棍数量为i时最小可以拼出dp[i]
int d[N];
int getmin(int x,int y){//对x和y进行操作,使其组成最小数
memset(d,0,sizeof(d));
int i=2;
while(x>0){
d[i++]=x%10;
x/=10;
}
int n=--i;
for(;i>=2;i--){
if(y==0&&i==n){
continue;
}
if(y<d[i]){
for(int j=1;j<=i-1;j++){
d[j]=d[j+1];
}
d[i]=y;
break;
}
if(i==2){
d[1]=y;
}
}
int ans=0;
for(;n>=1;n--){
ans=ans*10+d[n];
}
return ans;
}
int a[N]={6,2,5,5,4,5,6,3,7,6};
int main(){
int T;
cin>>T;
while(T--){
memset(dp,-1,sizeof(dp));
dp[2]=1;
dp[3]=7;
dp[4]=4;
dp[5]=2;
dp[6]=6;
dp[7]=8;
int n;
cin>>n;
if(n<=7){
cout<<dp[n]<<endl;
continue;
}
for(int i=2;i<=n;i++){
for(int j=9;j>=0;j--){
if(i-a[j]>=2){//¿ÉÒÔÆ´
// cout<<"i="<<i<<" "<<"a[j]="<<a[j]<<" ";
// int t=i-a[j];
// cout<<"dp["<<t<<"]="<<dp[i-a[j]]<<" "<<"j="<<j<<" ";
// cout<<"×îСÊý="<<getmin(dp[i-a[j]],j)<<endl;
dp[i]=min(dp[i],getmin(dp[i-a[j]],j));
}else{
continue;
}
}
}
cout<</*"answer:"<<*/dp[n]<<endl;
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...