貝殻は部屋を探して2020校は筆記試験のアルゴリズムの技師の筆記試験の問題を募集して木の鋸の斧を採って木を切ります
1184 ワード
問題は、あなたの前にn本の木が順番に並んでいますが、あなたは2つの道具を持っています.鋸と斧を持っています.彼らがi本目の木を切る時間はそれぞれaiとbiです.最初は斧を持っていましたが、i本目の木を切る前に道具を交換するのにciの時間がかかりました.問題が来ました.この木を順番に切る時間は最短でいくらですか.
入力
しゅつりょく
サンプル入力
サンプル出力
分析:この問題は状態遷移のdpであり、この比較的近いleetcode株の問題の中には、状態遷移でこの3つの株の問題を同時に解く問題がある.
具体的な分析はコード注釈の中で体現します
入力
n(n<=100)
n , ai,bi,ci(i<=30000)
しゅつりょく
サンプル入力
3
20 40 20
10 4 25
90 100 5
サンプル出力
139
分析:この問題は状態遷移のdpであり、この比較的近いleetcode株の問題の中には、状態遷移でこの3つの株の問題を同時に解く問題がある.
具体的な分析はコード注釈の中で体現します
#include
#include
#include
using namespace std;
int main()
{
int n;
cin>>n;
vector a(n+1), b(n+1), c(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i]>>c[i];
}
vector> dp; // 1, 0
dp.resize(n+1, vector(2));
dp[1][1] = b[1]; // 1
dp[1][0] = a[1] + c[1]; // 1 ,
for(int i=2; i<=n;i++)
{
dp[i][1] = min(dp[i-1][1], dp[i-1][0] + c[i]) + b[i];
dp[i][0] = min(dp[i-1][0], dp[i-1][1] + c[i]) + a[i];
}
cout<