【解题报告】[动态规划]RQNOJ - PID82 / 又上锁妖塔

 1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 int t[10005],n;
 5 int dp[10005][2];
 6 int min(int x,int y)
 7 {
 8     return x<y?x:y;
 9 }
10 int main()
11 {
12     int i;
13     cin>>n;
14     for(i=0;i<n;i++)
15     {
16         scanf("%d",&t[i]);
17     }
18     dp[0][1]=0;
19     dp[1][0]=0;
20     dp[1][1]=t[0];
21     for(i=2;i<=n;i++)
22     {
23         dp[i][0]=min(dp[i-1][1],dp[i-2][1]);
24         dp[i][1]=min(dp[i-1][0],dp[i-1][1])+t[i-1];
25         //printf("%d  %d\n",dp[i][0],dp[i][1]);
26     }
27     printf("%d\n",min(dp[n][0],dp[n][1]));
28     return 0;
29 }