Codeforces Round 71

「爱情、让人受尽委屈。」 2023-08-17 16:26 242阅读 0赞

第一题：读题+基础贪心

http://codeforces.com/contest/1207

第二题：思维题

题意：对于

第三题：

大佬们的dp写法：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 2e5+5;
  5. const int inf = 0x3f3f3f3f;
  6. ll T, n, a, b, dp[maxn][2];
  7. char s[maxn];
  8. int main()
  9. {
  10.     cin >> T;
  11.     while(T--) {
  12.         memset(dp, inf, sizeof(dp));
  13.         cin >> n >> a >> b;
  14.         scanf("%s", s+1);
  15.         dp[0][0] = b;
  16.         for (int i = 1; i <= n; i++) 
  17.         {
  18.             if (s[i] == '0') 
  19.             {
  20.                 dp[i][0] = min(dp[i][0], dp[i-1][0]+a+b);
  21.                 dp[i][0] = min(dp[i][0], dp[i-1][1]+2*a+2*b);
  22.                 dp[i][1] = min(dp[i][1], dp[i-1][0]+2*a+b);
  23.             }
  24.             dp[i][1] = min(dp[i][1], dp[i-1][1]+a+2*b);
  25.         }
  26.         cout << dp[n][0] << endl;
  27.     }
  28.      return 0;
  29. }

转载于:https://www.cnblogs.com/Aiahtwo/p/11407242.html

发表评论

表情：
评论列表 （有 0 条评论，242人围观）

还没有评论，来说两句吧...

相关阅读