本文共 1449 字,大约阅读时间需要 4 分钟。
给出n个数,奇数次操作x,y都加上a[x],偶数次操作y加上a[x],x减去a[x],走出了范围就结束。
问结束时的y值,如果无法结束,那么输出-1#include#include #include #include #define MAX 200007using namespace std;typedef long long LL;LL dp[MAX][2];int vis[MAX][2];int a[MAX],n;void dfs ( int x , int d ){ if ( vis[x][d%2] ) return; vis[x][d%2] = 1; if ( d&1 ) { int y = x-a[x]; if ( y <= 0 ) { dp[x][d%2] = a[x]; return; } dfs ( y , d+1 ); if ( dp[y][(d+1)%2] != -1 ) dp[x][d%2] = dp[y][(d+1)%2] + a[x]; } else { int y = x+a[x]; if ( y > n ) { dp[x][d%2] = a[x]; return; } dfs ( y , d+1 ); if ( dp[y][(d+1)%2] != -1 ) dp[x][d%2] = dp[y][(d+1)%2] + a[x]; }}int main ( ){ while ( ~scanf ( "%d" , &n ) ) { for ( int i = 2 ; i <= n ; i++ ) scanf ( "%d" , &a[i] ); memset ( vis , 0 , sizeof ( vis ) ); memset ( dp , -1, sizeof ( dp ) ); dp[1][0] = -1; vis[1][0] = 1; dp[1][1] = 0; vis[1][1] = 1; for ( int i = 2 ; i <= n ; i++ ) dfs ( i , 1 ); for ( int i = 2 ; i <= n ; i++ ) if ( dp[i][1] != -1 ) dp[i][1] += i-1; for ( int i = 2 ; i <= n ; i++ ) printf ( "%lld\n" , dp[i][1] ); }}
转载地址:http://aqvjn.baihongyu.com/