公交汽车动态规划c++

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<utility>

#include<map>

using namespace std;

int price[15];

int dp[105];

int n;

int main(){

for(int i=1;i<=10;i++){

scanf("%d",&price[i]); 

}

cin>>n;

dp[1]=price[1];

for(int i=2;i<=10;i++){

int minn=dp[1]+dp[i-1];

for(int j=1;j<=i-1;j++){

if(dp[j]+dp[i-j]<minn){

minn=dp[j]+dp[i-j];

}

}

dp[i]=min(minn,price[i]);

}

if(n<=10){

cout<<dp[n]<<endl;

return 0;

}

for(int i=11;i<=n;i++){

int cnt=dp[i-1]+dp[1];

for(int j=1;j<=10;j++){

if(dp[i-j]+dp[j]<cnt){

cnt=dp[i-j]+dp[j];

}

}

dp[i]=cnt;

}

    cout<<dp[n]<<endl;

return 0;

}