Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
28311 | 22fhq | 【J】T2 | C++ | 通过 | 100 | 10 MS | 1684 KB | 1095 | 2024-04-14 13:39:39 |
#include<bits/stdc++.h> using namespace std; int n,p[100005],ans1; int f[100005],j[100005]; int main(){ // auto input=freopen("ahaha.in","r",stdin); // auto output=freopen("ahaha.out","w",stdout); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++){ cin>>p[i]; f[i]=i; j[i]=1e9; } f[1]=0; j[n+1]=1e9; f[n+1]=n+1; for(int i=1;i<=n;i++){ for(int j=i;j<=min(n+1,i+p[i]);j++){ f[j]=f[i]; } } for(int i=1;i<=n+1;i++){ if(i+p[i]<=n&&j[i+p[i]+1]==1000000000){ j[i+p[i]+1]=i; // cout<<i+p[i]+1<<" "<<i<<endl; } j[i]=min(j[i],j[f[i]]); // cout<<j[i]<<" "; } stack<int>a; int now=n+1; now=j[now]; while(now){ // cout<<now<<" "; a.push(now); now=j[now]; } cout<<a.size()<<endl; while(a.size()){ cout<<a.top()<<" "; a.pop(); } return 0; } /* jp1 jp2 jp3 jp4 jp5 jp6 jp7 jp8akioi */