存在n+1个房间,每个房间依次为房间1 2 3...i,每个房间都存在一个传送门,i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问),每次移动他有两种移动策略:
A. 如果访问过当前房间 i 偶数次,那么下一次移动到房间i+1;
B. 如果访问过当前房间 i 奇数次,那么移动到房间pi;
现在路人甲想知道移动到房间n+1一共需要多少次移动;
第一行包括一个数字n(30%数据1<=n<=100,100%数据 1<=n<=1000),表示房间的数量,接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。
输出一行数字,表示最终移动的次数,最终结果需要对1000000007 (10e9 + 7) 取模。
2 1 2
4
开始从房间1 只访问一次所以只能跳到p1即 房间1, 之后采用策略A跳到房间2,房间2这时访问了一次因此采用策略B跳到房间2,之后采用策略A跳到房间3,因此到达房间3需要 4 步操作。
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] ps = new int[n + 1]; int index = 1; while (index <= n) { ps[index ++] = sc.nextInt(); } long[] dp = new long[n + 1]; dp[0] = 0L; dp[1] = 2L; for (int i = 2; i <= n; i ++) { dp[i] = 2 * dp[i - 1] - dp[ps[i] - 1] + 2; dp[i] = dp[i] < 0 ? dp[i] + 1000000007 : dp[i] % 1000000007; } System.out.println(dp[n]); } }
import java.util.*; public class ChuanSongMen { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n+1]; int[] dp = new int[n+1]; dp[0] = 0; int mod = 1000000007; for(int i = 1;i<=n;i++){ nums[i] = sc.nextInt(); /** * dp[i-1]+1 第一次到达i, * +1 跳回nums[i] * 此时nums[i]奇数次,nums[i]之后到i-1都是偶数次 * 此时和第一次到达nums[i]的情况完全相同 * -1 到达nums[i]-1 就相当于 nums[i]也是偶数 从nums[i]到i-1都是偶数 * +(dp[i-1]-dp[nums[i]-1]) 从nums[i]-1 到达i-1且i-1还是偶数次 * +1 爹第二次到达 i即为所求 * 总体上 dp[i] = dp[i-1]+1+1-1+(dp[i-1]-dp[nums[i]-1])+1; * 汇总 * dp[i] = 2*dp[i-1]+2-dp[nums[i]-1]; */ dp[i] = (2*dp[i-1]-dp[nums[i]-1]+2)%mod; } dp[n] = dp[n]>0?dp[n]:dp[n]+mod; System.out.println(dp[n]); } }
//直接求解可以通过60% public static void main(String[] args) { Scanner in=new Scanner(System.in); int roomNum=in.nextInt(); int[] visitedNum=new int[roomNum]; int[] transferDoor=new int[roomNum]; for(int i=0;i<roomNum;i++) { transferDoor[i]=in.nextInt()-1; } int movingCount=0;//移动次数 //从第一个房间开始 第一个房间已经过问过一次 visitedNum[0]=0; int roomID=0; while(roomID!=roomNum) { visitedNum[roomID]+=1; movingCount++; if(visitedNum[roomID]%2==0) { roomID+=1; } else { roomID=transferDoor[roomID]; } } System.out.println(movingCount%1000000007); }