题解 | #附加题#
附加题
https://www.nowcoder.com/practice/58b04ed2865f4ff4921290f1bd4ee486
#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
