社区讨论

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 条回复,欢迎继续交流。

正在加载回复...