牛牛的跳跳棋
  • 板块学术版
  • 楼主dome1
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/10/4 15:58
  • 上次更新2023/11/4 04:53:36
查看原帖
牛牛的跳跳棋
478380
dome1楼主2021/10/4 15:58
using namespace std;
int ans,tot;
int sum[100010];
int n;
int p[110];
int f[100010];
int find(int y);
int dp(int x)
{
	for(int i=1;i<x;i++)
	{
		for(int j=1;j<=p[i];j++)
				f[i+j]=min(f[i+j],f[i]+1);
	}
	if(f[x]!=0x3f3f3f3f)
	{
		if(ans==0)	cout<<"0";
		else
		{
			cout<<ans<<endl;
			for(int i=1;i<=ans;i++)
			{
				cout<<sum[i]<<" ";
			}
		}
	}
	else
	{
		find(x);
	}
}
int find(int y)
{
	int z=0;
	for(int i=1;i<y;i++)
	{
		for(int j=1;j<=p[i];j++)
		{
			if(i+p[j]+1==y)
			{
				z=i;
				break;
			}
		}
		if(z!=0)
			break;
	}
	sum[++ans]=z;
	dp(z);
}
int main()
{
//	freopen("tiaotq.in","r",stdin);
//	freopen("tiaotq.out","w",stdout);
	cin>>n;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		cin>>p[i];
	}
	f[0]=0;
	dp(n+1);
}```
求助QAQ
2021/10/4 15:58
加载中...