题解 | #附加题#

#include "iostream"
#include "vector"
#include "cmath"

using namespace std;

//动态规划
int main(int argv, char* argc[])
{
    uint16_t roomTotalNum = 0;
    unsigned long long countTotal = 0;
    vector<int64_t> roomCountList;
    vector<uint16_t> piList;
    uint16_t piTemp = 0;
    uint16_t n = 0;
    uint16_t roomCurrNo = 1;
    int64_t modVal = 1000000007;
    cin >> n;
    roomTotalNum = n+1;
    roomCountList.push_back(0);    //0号
    piList.push_back(0);
    while(n--)
    {
        cin >> piTemp;
        piList.push_back(piTemp);
        roomCountList.push_back(0);
    }
    roomCountList.push_back(0);
    while(roomCurrNo < roomTotalNum + 1)
    {
        if (roomCurrNo < 2)
            roomCountList[1] = 0;
        else
        {
            roomCountList[roomCurrNo] = 
                roomCountList[roomCurrNo - 1]
                * 2 
                - roomCountList[piList[roomCurrNo - 1]]
                + 2;
            if (roomCountList[roomCurrNo] < 0)
                roomCountList[roomCurrNo] += modVal;
            else
                roomCountList[roomCurrNo] %= modVal;
        }
        roomCurrNo++;
    }
    countTotal = roomCountList[roomCurrNo - 1];
    cout << countTotal % modVal << endl;
    return 0;
}
//暴力解法行不通
#if 0
int main(int argv, char* argc[])
{
    uint16_t roomTotalNum = 0;
    unsigned long long countTotal = 0;
    vector<uint32_t> roomCountList;
    vector<uint16_t> piList;
    uint16_t piTemp = 0;
    uint16_t n = 0;
    uint16_t roomCurrNo = 1;
    cin >> n;
    roomTotalNum = n+1;
    roomCountList.push_back(0);    //0号
    piList.push_back(0);
    while(n--)
    {
        cin >> piTemp;
        piList.push_back(piTemp);
        roomCountList.push_back(0);
    }
    while(roomCurrNo < roomTotalNum)
    {
        roomCountList[roomCurrNo]++;
        countTotal++;
        if (roomCountList[roomCurrNo] % 2 == 0)
            roomCurrNo++;
        else
            roomCurrNo = piList[roomCurrNo];
    }
    cout << countTotal % 1000000007 << endl;
    return 0;
}
#endif