这场确实被教育了，自己的缺点暴露无遗，菜也暴露无遗，给我敲响了一个警钟。
题目链接
Educational Codeforces Round 71 (Rated for Div. 2)
C
思路
DP，dp[0][i]表示第i个位置高度为1的最低花费，dp[1][i]表示第i个位置高度为2的最低花费
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5+10;
ll dp[maxn][2];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,a,b;
scanf("%d %d %d",&n,&a,&b);
string s;
cin>>s;
for(int i=0;i<=n;i++)
for(int j=0;j<2;j++)
dp[i][j]=1e18;
dp[0][0]=b;
dp[0][1]=1e18;
for(int i=1;i<=n;i++)
{
if(s[i-1]=='1')
{
dp[i][1]=b+b+dp[i-1][1]+a;
}
else
{
dp[i][1]=min(dp[i-1][1]+b+b+a,dp[i-1][0]+a+a+b+b);
dp[i][0]=min(dp[i-1][1]+a+b+a,dp[i-1][0]+a+b);
}
}
cout<<dp[n][0]<<endl;
}
}
|