• AtCoder Beginner Contest 228（A-Ex）

    A - On and Off (atcoder.jp)

            （1）题意

                    高桥每天在S点钟打开他房间的灯，并在T点钟关灯，指示灯亮起时，日期可能会发生改变，判断是否在X点过后30分时亮着。

            （2）思路

                    直接模拟即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. void solve()
    16. {
    17.     int s,t,x;
    18.     cin >> s >> t >> x;
    19.     for(int i = s;i != t;i ++) {
    20.         if(i == 24) i = 0;
    21.         if(x == i) {
    22.             cout << "Yes";
    23.             return;
    24.         }
    25.     }
    26.     cout << "No";
    27. }
    28. int main()
    29. {
    30.     ios::sync_with_stdio(false);
    31.     cin.tie(0),cout.tie(0);
    32.     int T = 1;
    33.     // cin >> T;
    34.     while(T --) solve();
    35.     return 0;
    36. }

    B - Takahashi's Secret (atcoder.jp)

            （1）题意

                    高桥有N个朋友，刚开始x这个朋友这个人会知道这个秘密，然后每个人在第i个位置会告诉p[i]这个位置的人高桥的秘密，问最后高桥的朋友会有多少知道秘密。

            （2）思路

                    对于X这个位置，一直往p[i]这个位置跳即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. int p[N],vis[N];
    16. void solve()
    17. {
    18.     int n,x;
    19.     cin >> n >> x;
    20.     rep(i,1,n) cin >> p[i];
    21.     int c = 0;
    22.     while(!vis[x]) {
    23.         vis[x] = true;
    24.         c ++;
    25.         x = p[x];
    26.     }
    27.     cout << c;
    28. }
    29. int main()
    30. {
    31.     ios::sync_with_stdio(false);
    32.     cin.tie(0),cout.tie(0);
    33.     int T = 1;
    34.     // cin >> T;
    35.     while(T --) solve();
    36.     return 0;
    37. }

    C - Final Day (atcoder.jp)

            （1）题意

                    N名学生参加四天考试，每天考试总分300分，现在前三天考试已经结束，让你预测每个学生的总分的排名是否是Top K。

            （2）思路

                    直接把前三门成绩全部相加，然后排个序，对于每个人直接+300看能否达到Top K即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. ll p[N],z[N];
    16. void solve()
    17. {
    18.     int n,k;
    19.     cin >> n >> k;
    20.     int x;
    21.     rep(i,1,n) {
    22.         rep(j,1,3) {
    23.             cin >> x;
    24.             p[i] += x;
    25.         }
    26.         z[i] = p[i];
    27.     }
    28.     sort(z + 1,z + 1 + n);
    29.     rep(i,1,n) {
    30.         int idx = upper_bound(z + 1,z + 1 + n,p[i] + 300) - z;
    31.         if(n + 1 - idx < k) cout << "Yes\n";
    32.         else cout << "No\n";
    33.     }
    34. }
    35. int main()
    36. {
    37.     ios::sync_with_stdio(false);
    38.     cin.tie(0),cout.tie(0);
    39.     int T = 1;
    40.     // cin >> T;
    41.     while(T --) solve();
    42.     return 0;
    43. }

    D - Linear Probing (atcoder.jp)

            （1）题意

                            有一个长为2^20的序列，初始全部位置为-1，对于第Q个查询，会有两种类型。

    第一种类型，定义一个Xi，若Axi%N这个位置不为-1，则往下找到第一个不为-1的数组，把那个位置值设置为Xi。第二种类型就是输出低Xi这个位置值是多少。

            （2）思路

                            用一个set维护一下每个为-1的位置，对于第一个类型的查询，我们直接二分一下那个位置即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e6 + 10;
    15. ll v[N];
    16. void solve()
    17. {
    18.     set<int> st;
    19.     int n = (1 << 20) - 1;
    20.     rep(i,0,n) {
    21.         v[i] = -1;
    22.         st.insert(i);
    23.     }
    24.     int q;
    25.     n ++;
    26.     cin >> q;
    27.     while(q --) {
    28.         ll ti,xi;
    29.         cin >> ti >> xi;
    30.         if(ti == 2) cout << v[xi % n] << '\n';
    31.         else {
    32.             int cur = xi % n;
    33.             auto it = st.lower_bound(cur);
    34.             if(it != st.end()) {
    35.                 v[*it] = xi;
    36.                 st.erase(it);
    37.             }
    38.             else {
    39.                 it = st.lower_bound(0);
    40.                 v[*it] = xi;
    41.                 st.erase(it);
    42.             }
    43.         }
    44.     }
    45. }
    46. int main()
    47. {
    48.     ios::sync_with_stdio(false);
    49.     cin.tie(0),cout.tie(0);
    50.     int T = 1;
    51.     // cin >> T;
    52.     while(T --) solve();
    53.     return 0;
    54. }

    E - Integer Sequence Fair (atcoder.jp)

            （1）题意

                    计算M^{K^N}。

            （2）思路

                    考虑先计算上面部分的指数K^N,若不要对下面M产生影响，我们可以使用欧拉降幂，对于K^N进行快速幂取模998244352即可，然后用下面的再计算一次快速幂取模998244353即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. const ll mod = 998244353;
    16. using i128 = __int128;
    17. ll ksm(ll a,ll b,ll p)
    18. {
    19.     if(!a) return 0;
    20.     i128 rs = 1;
    21.     while(b) {
    22.         if(b & 1) rs = rs % p * a % p;
    23.         a = (i128)a % p * a % p;
    24.         b >>= 1;
    25.     }
    26.     return (ll)rs;
    27. }
    28. void solve()
    29. {
    30.     ll n,k,m;
    31.     cin >> n >> k >> m;
    32.     k %= (mod - 1),m %= (mod);
    33.     ll z = ksm(k,n,mod - 1);
    34.     cout << ksm(m,z,mod) << '\n';
    35. }
    36. int main()
    37. {
    38.     ios::sync_with_stdio(false);
    39.     cin.tie(0),cout.tie(0);
    40.     int T = 1;
    41.     // cin >> T;
    42.     while(T --) solve();
    43.     return 0;
    44. }

    F - Stamp Game (atcoder.jp)

            （1）题意

                    给你个H*W的矩形，每个格子里面有一个数，问你选择一个H1*W1的矩形去掉一个H2*W2的矩形后，最多能取多大的值。

            （2）思路

                    二维RMQ问题，因此直接上二维ST即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 1003;
    15. ll s[N][N],a[N][N],val[N][N];
    16.  
    17. ll dp[N][N][11][11];
    18. int num[N];
    19. void rmq(int n, int m){
    20.     int nn = log2(n), mm = log2(m);
    21.     for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) dp[i][j][0][0] = val[i][j];
    22.     for(int ii=0; ii<=nn; ii++)
    23.     for(int jj=0; jj<=mm; jj++)
    24.     if(ii + jj) {
    25.         for(int i=1; i+(1<-1 <= n; i++)
    26.         for(int j=1; j+(1<-1 <= m; j++) {
    27.             if(ii) dp[i][j][ii][jj] = max(dp[i][j][ii-1][jj], dp[i+(1<<(ii-1))][j][ii-1][jj]);
    28.             else dp[i][j][ii][jj] = max(dp[i][j][ii][jj-1], dp[i][j+(1<<(jj-1))][ii][jj-1]);
    29.         }
    30.     }
    31. }
    32. ll query(int x1, int y1, int x2, int y2){
    33.     // ll res = 0;
    34.     // rep(i,x1,x2) rep(j,y1,y2) {
    35.     //     res = max(res,val[i][j]);
    36.     // }
    37.     // return res;
    38.     int k1 = log2(x2-x1+1); //num[x2-x1+1];
    39.     int k2 = log2(y2-y1+1); //num[y2-y1+1];
    40.     x2 = x2 - (1<1;
    41.     y2 = y2 - (1<1;
    42.     ll ans1 = max(dp[x1][y1][k1][k2], dp[x1][y2][k1][k2]);
    43.     ll ans2 = max(dp[x2][y1][k1][k2], dp[x2][y2][k1][k2]);
    44.     return max(ans1, ans2);
    45. }
    46. ll get(int x1,int y1,int x2,int y2)
    47. {
    48.     return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    49. }
    50. void solve()
    51. {
    52.     int n,m,h1,h2,w1,w2;
    53.     cin >> n >> m >> h1 >> w1 >> h2 >> w2;
    54.     h2 = min(h2,h1),w2 = min(w2,w1);
    55.     rep(i,1,n) {
    56.         rep(j,1,m) {
    57.             cin >> a[i][j];
    58.             s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
    59.         }
    60.     }
    61.     rep(i,h2,n) rep(j,w2,m) {
    62.         val[i][j] = get(i - h2 + 1,j - w2 + 1,i,j);
    63.     }
    64.     rmq(n,m);
    65.     ll Ans = 0;
    66.     rep(i,h1,n) rep(j,w1,m) {
    67.         ll s1 = get(i - h1 + 1,j - w1 + 1,i,j);
    68.         ll s2 = query(i - (h1 - h2),j - (w1 - w2),i,j);
    69.         Ans = max(Ans,s1 - s2);
    70.     }
    71.     cout << Ans;
    72. }
    73. int main()
    74. {
    75.     ios::sync_with_stdio(false);
    76.     cin.tie(0),cout.tie(0);
    77.     int T = 1;
    78.     // cin >> T;
    79.     while(T --) solve();
    80.     return 0;
    81. }

    G - Digits on Grid (atcoder.jp)

            （1）题意

                    有一个H*W的网格，高桥每次可以把一个棋子移到同一行的某一个位置，青木每次会把棋子移动到同一列的某一个位置，在移动2*N步后，会产生多少个不同的数字序列。

            （2）思路

                    对于这些操作来说，实际上是在二分图上走，把行列抽象成不同点，那我们分别对每一步进行dp，定义dp[S]表示目前经过的某一个数字会到达哪些可用行/列，初始化dp[(1 << H) - 1] = 1。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 11;
    15. int a[N][N];
    16. vector<int> row[N][N],col[N][N];
    17. using i64 = long long;
    18.  
    19. constexpr int P = 998244353;
    20. // assume -P <= x < 2P
    21. int Vnorm(int x) {
    22.     if (x < 0) {
    23.         x += P;
    24.     }
    25.     if (x >= P) {
    26.         x -= P;
    27.     }
    28.     return x;
    29. }
    30. template<class T>
    31. T power(T a, i64 b) {
    32.     T res = 1;
    33.     for (; b; b /= 2, a *= a) {
    34.         if (b % 2) {
    35.             res *= a;
    36.         }
    37.     }
    38.     return res;
    39. }
    40. struct Mint {
    41.     int x;
    42.     Mint(int x = 0) : x(Vnorm(x)) {}
    43.     Mint(i64 x) : x(Vnorm(x % P)) {}
    44.     int val() const {
    45.         return x;
    46.     }
    47.     Mint operator-() const {
    48.         return Mint(Vnorm(P - x));
    49.     }
    50.     Mint inv() const {
    51.         assert(x != 0);
    52.         return power(*this, P - 2);
    53.     }
    54.     Mint &operator*=(const Mint &rhs) {
    55.         x = i64(x) * rhs.x % P;
    56.         return *this;
    57.     }
    58.     Mint &operator+=(const Mint &rhs) {
    59.         x = Vnorm(x + rhs.x);
    60.         return *this;
    61.     }
    62.     Mint &operator-=(const Mint &rhs) {
    63.         x = Vnorm(x - rhs.x);
    64.         return *this;
    65.     }
    66.     Mint &operator/=(const Mint &rhs) {
    67.         return *this *= rhs.inv();
    68.     }
    69.     friend Mint operator*(const Mint &lhs, const Mint &rhs) {
    70.         Mint res = lhs;
    71.         res *= rhs;
    72.         return res;
    73.     }
    74.     friend Mint operator+(const Mint &lhs, const Mint &rhs) {
    75.         Mint res = lhs;
    76.         res += rhs;
    77.         return res;
    78.     }
    79.     friend Mint operator-(const Mint &lhs, const Mint &rhs) {
    80.         Mint res = lhs;
    81.         res -= rhs;
    82.         return res;
    83.     }
    84.     friend Mint operator/(const Mint &lhs, const Mint &rhs) {
    85.         Mint res = lhs;
    86.         res /= rhs;
    87.         return res;
    88.     }
    89.     friend std::istream &operator>>(std::istream &is, Mint &a) {
    90.         i64 v;
    91.         is >> v;
    92.         a = Mint(v);
    93.         return is;
    94.     }
    95.     friend std::ostream &operator<<(std::ostream &os, const Mint &a) {
    96.         return os << a.val();
    97.     }
    98. };
    99. void solve()
    100. {
    101.     int n,m,k;
    102.     cin >> n >> m >> k;
    103.     k <<= 1;
    104.     rep(i,0,n - 1) rep(j,0,m - 1) {
    105.         char c;
    106.         cin >> c;
    107.         a[i][j] = c - '0';
    108.     }
    109.     rep(i,0,n - 1) rep(j,0,m - 1) {
    110.         row[i][a[i][j]].pb(j);
    111.         col[j][a[i][j]].pb(i);
    112.     }
    113.     vector dp(1 << n,0);
    114.     dp[(1 << n) - 1] = 1;
    115.     rep(i,1,k) {
    116.         if(i & 1) {
    117.             vector ndp(1 << m,0);
    118.             rep(S,1,(1 << n) - 1) {
    119.                 if(!dp[S].val()) continue;
    120.                 rep(dig,1,9) {
    121.                     int T = 0;
    122.                     rep(j,0,n - 1) {
    123.                         if(!(S >> j & 1)) continue;
    124.                         for(auto p : row[j][dig]) T |= 1 << p;
    125.                     }
    126.                     ndp[T] += dp[S];
    127.                 }
    128.             }
    129.             dp = ndp;
    130.         }
    131.         else {
    132.             vector ndp(1 << n,0);
    133.             rep(S,1,(1 << m) - 1) {
    134.                 if(!dp[S].val()) continue;
    135.                 rep(dig,1,9) {
    136.                     int T = 0;
    137.                     rep(j,0,m - 1) {
    138.                         if(!(S >> j & 1)) continue;
    139.                         for(auto p : col[j][dig]) T |= 1 << p;
    140.                     }
    141.                     ndp[T] += dp[S];
    142.                 }
    143.             }
    144.             dp = ndp;
    145.         }
    146.     }
    147.     Mint Ans = 0;
    148.     for(int i = 1;i < (1 << n);i ++) {
    149.         Ans += dp[i];
    150.     }
    151.     cout << Ans;
    152. }
    153. int main()
    154. {
    155.     ios::sync_with_stdio(false);
    156.     cin.tie(0),cout.tie(0);
    157.     int T = 1;
    158.     // cin >> T;
    159.     while(T --) solve();
    160.     return 0;
    161. }

    H - Histogram (atcoder.jp)

            （1）题意

                    给你两个长度为N的整数序列A和C，你可以操作任意次，每次选择一个整数i，使得A[i] + 1，花费Ci元，完成操作后你需要支付K*X元，K是A元素中不同值得个数。

            （2）思路

                    我们对于每一个序列按A为第一关键字排序。考虑某一段数把前面得都变成当前位置得值，那么这个题就转换成了把这个序列划分成多少段得问题。

                    因此考虑dp[i]表示把前i段划分好后，最少需要花费多少元？ 

                    dp[i] = dp[j] + \sum_{k = j + 1}^{i}(a[i] - a[k]) * c[k] + x

                    化简一下

                    dp[i] = dp[j] + a[i] * \sum_{k = j + 1}^{i}c[k] - \sum_{k = j + 1} ^ {i}a[k] * c[k] + x   

                    dp[i] = dp[j] + a[i] * (sumC[i] - sumC[j]) - sumCA[i] + sumCA[j] + x                          考虑前缀和维护sumC和sumCA，对于有j得项抽出来。

                    设dp[j] + sumCA[j]为b     -sumC[j]为k

                    发现这个东西可以用斜率优化掉，因此直接上李超树即可。

         （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. namespace OY {
    16.     struct LichaoSegLine {
    17.         double m_k, m_b;
    18.         LichaoSegLine() = default;
    19.         LichaoSegLine(double k, double b) : m_k(k), m_b(b) {}
    20.         double calc(int i) const { return m_k * i + m_b; }
    21.     };
    22.     template <typename Line>
    23.     struct LichaoSegLess {
    24.         bool operator()(const Line &x, const Line &y, int i) const { return x.calc(i) < y.calc(i); }
    25.     };
    26.     template <typename Line = LichaoSegLine, typename Compare = LichaoSegLess>
    27.     struct LichaoSegTree {
    28.         struct LineNode {
    29.             Line m_line;
    30.             LineNode *m_lchild, *m_rchild;
    31.             LineNode(Line line, LineNode *lchild = nullptr, LineNode *rchild = nullptr) : m_line(line), m_lchild(lchild), m_rchild(rchild) {}
    32.         };
    33.         Line m_defaultLine;
    34.         uint64_t m_length;
    35.         Compare m_comp;
    36.         LineNode *m_root;
    37.         void _clear(LineNode *p) {
    38.             // if (p->m_lchild) _clear(p->m_lchild);
    39.             // if (p->m_rchild) _clear(p->m_rchild);
    40.             // delete p;
    41.         }
    42.         LichaoSegTree(uint64_t length = 0, Compare comp = Compare(), Line defaultLine = Line()) : m_comp(comp), m_defaultLine(defaultLine), m_root(nullptr) { resize(length); }
    43.         ~LichaoSegTree() {
    44.             if (m_root) _clear(m_root);
    45.         }
    46.         void resize(uint64_t length) {
    47.             if (m_root) _clear(m_root);
    48.             m_root = (m_length = length) ? new LineNode(m_defaultLine, nullptr, nullptr) : nullptr;
    49.         }
    50.         void add(uint64_t left, uint64_t right, const Line &line) {
    51.             if (right >= m_length) right = m_length - 1;
    52.             if (left > right) return;
    53.             auto dfs = [&](auto self, LineNode *&cur, uint64_t lbound, uint64_t rbound, Line line) -> void {
    54.                 if (!cur) cur = new LineNode(m_defaultLine, nullptr, nullptr);
    55.                 if (uint64_t mid = (lbound + rbound) / 2; left <= lbound && right >= rbound) {
    56.                     if (m_comp(cur->m_line, line, mid)) std::swap(cur->m_line, line);
    57.                     if (lbound < rbound)
    58.                         if (m_comp(cur->m_line, line, lbound))
    59.                             self(self, cur->m_lchild, lbound, mid, line);
    60.                         else if (m_comp(cur->m_line, line, rbound))
    61.                             self(self, cur->m_rchild, mid + 1, rbound, line);
    62.                 } else {
    63.                     if (left <= mid) self(self, cur->m_lchild, lbound, mid, line);
    64.                     if (right > mid) self(self, cur->m_rchild, mid + 1, rbound, line);
    65.                 }
    66.             };
    67.             dfs(dfs, m_root, 0, m_length - 1, line);
    68.         }
    69.         Line query(uint64_t i) const {
    70.             Line res(m_defaultLine);
    71.             auto dfs = [&](auto self, LineNode *cur, uint64_t lbound, uint64_t rbound) -> void {
    72.                 if (!cur) return;
    73.                 if (m_comp(res, cur->m_line, i))
    74.                     res = cur->m_line;
    75.                 if (lbound == rbound) return;
    76.                 if (uint64_t mid = (lbound + rbound) / 2; i <= mid)
    77.                     self(self, cur->m_lchild, lbound, mid);
    78.                 else
    79.                     self(self, cur->m_rchild, mid + 1, rbound);
    80.             };
    81.             dfs(dfs, m_root, 0, m_length - 1);
    82.             return res;
    83.         }
    84.     };
    85.     template <typename Line = LichaoSegLine, typename Compare = LichaoSegLess>
    86.     LichaoSegTree(uint64_t = 0, Compare = Compare(), Line = Line()) -> LichaoSegTree;
    87. }
    88. using i128 = __int128;
    89. struct Line {
    90.     ll k,b;
    91.     ll calc(ll i) const {
    92.         return i * k + b;
    93.     }
    94. };
    95.  struct compare {
    96.     bool operator()(const Line &x, const Line &y, i128 i) const {
    97.         ll x_val = x.calc(i), y_val = y.calc(i);
    98.         return x_val > y_val;
    99.     }
    100. };
    101. const uint64_t inf = 1e12;
    102. pair e[N];
    103. ll sumC[N],sumCA[N];
    104. ll dp[N];
    105. void solve()
    106. {
    107.     int n,x;
    108.     cin >> n >> x;
    109.     //dp[i]:前i个的最小花费
    110.     //dp[i] = dp[j] + k:[j + 1,i](a[i] - a[k])*c[k] + x
    111.     //dp[i] = dp[j] + a[i] * k:[j + 1,i]c[k] - k:[j + 1,i]:a[k] * c[k] + x
    112.     //dp[i] = dp[j] + a[i] * (sumC[i] - sumC[j]) - sumCA[i] + sumCA[j] + x
    113.     //dp[i] = dp[j] + a[i] * sumC[i] - a[i] * sumC[j] - sumCA[i] + sumCA[j] + x
    114.     //设dp[j] + sumCA[j]为b -sumC[j]为k
    115.     //则dp[i] = b + a[i] * sumC[i] - a[i] * k - sumCA[i] + x
    116.     //根据a[i] query一个最小的值进行转移即可
    117.     OY::LichaoSegTree tr(1000005,compare(),Line{0,inf});
    118.     for(int i = 1;i <= n;i ++) {
    119.         cin >> e[i].fi >> e[i].se;
    120.     }
    121.     sort(e + 1,e + 1 + n);
    122.     for(int i = 1;i <= n;i ++) {
    123.         sumC[i] = sumC[i - 1] + e[i].se;
    124.         sumCA[i] = sumCA[i - 1] + 1ll * e[i].fi * e[i].se;
    125.     }
    126.     tr.add(0,inf,{0,0});
    127.     for(int i = 1;i <= n;i ++) {
    128.         dp[i] = 1ll * e[i].fi * sumC[i] + tr.query(e[i].fi).calc(e[i].fi) - sumCA[i] + x;
    129.         tr.add(0,inf,{-sumC[i],dp[i] + sumCA[i]});
    130.     }
    131.     cout << dp[n] << '\n';
    132. }
    133. int main()
    134. {
    135.     ios::sync_with_stdio(false);
    136.     cin.tie(0),cout.tie(0);
    137.     int T = 1;
    138.     // cin >> T;
    139.     while(T --) solve();
    140.     return 0;
    141. }

  • 相关阅读:
    ffmpeg静态编译 —— 筑梦之路
    RFID系统简介：优点、应用与发展前景
    CADD课程学习（6）-- 获得已有的虚拟化合物库（Drugbank、ZINC）
    2024年最新通信安全员考试题库
    Achronix与您相约“2023全球AI芯片峰会”
    实时大数据处理real-time big data processing (RTDP)框架：挑战与解决方案
    借助ChatGPT撰写学术论文，如何设定有效的角色提示词指
    基于单片机声光控智能路灯系统仿真设计
    【Spring boot 普通类调用 Bean】
    系列四、Java8的Lambda表达式
  • 原文地址：https://blog.csdn.net/scanner___yw/article/details/133633575