1. 会和

    可以直接遍历
    学习一下二分
    0faf5e912141e9e4f2019a85ab4aaf8.jpg

    1. 7的倍数

    k = (j + nums[i]) % 7 < 0 ? (j + nums[i]) % 7 + 7 : (j + nums[i]) % 7
    dp[i][k]
    7cca8d61880036f166507ae16c94ee8.jpg1362941c51d58765e413e098f4ed26a.jpg

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. typedef long long ll;
    4. const int maxn= 1e6+7 ;
    5. const int inf = 0x3f3f3f3f;
    6. int n , a[maxn];
    7. int dp[maxn][10];
    8. int main(){
    9.     scanf("%d",&n);
    10.     for(int i = 1; i <= n; i ++){
    11.         scanf("%d",&a[i]);
    12.     }
    13.     memset(dp , -inf , sizeof(dp));
    14.     dp[0][0] = 0;
    15.     for(int i = 1; i <= n; i ++){
    16.         for(int j = 0; j < 7; j ++){
    17.             dp[i][j] = max(dp[i][j] , dp[i - 1][j]);
    18.             dp[i][j] = max(dp[i][j] , dp[i - 1][((j - a[i]) % 7 + 7) % 7] + a[i]);
    19.             //printf ("%d %d %d\n",i , j , dp[i][j]);
    20.         }
    22.     }
    23.     printf ("%d\n",dp[n][0]);
    24. }
    1. 中位数

    1df006eb6ae0c3bda86f021134f99d0.jpge2495da38c1d6ccf547a71a8017352e.jpg

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. typedef long long ll;
    4. const int maxn= 1e6+7 ;
    5. const int inf = 0x3f3f3f3f;
    6. int n , a[maxn];
    7. priority_queue<int>q1,q2;
    8. void init(){
    9.     while(q1.size()) q1.pop();
    10.     while(q2.size()) q2.pop();
    11. }
    12. void add(int now){
    13.     if(q2.size() == 0){
    14.         q2.push(-now);
    15.         return ;
    16.     }
    17.     if(now >= -q2.top()){
    18.         q2.push(-now);
    19.         if(q2.size() > q1.size() + 1){
    20.             int x = q2.top();
    21.             q2.pop();
    22.             q1.push(-x);
    23.         }
    24.     }
    25.     else{
    26.         q1.push(now);
    28.         if(q1.size() > q2.size()){
    29.             int x = q1.top();
    30.             q1.pop();
    31.             q2.push(-x);
    32.         }
    33.     }
    34. }
    35. int main(){
    36.     scanf("%d",&n);
    37.     ll ans = 0;
    38.     for(int i = 1; i <= n; i ++){
    39.         scanf("%d",&a[i]);
    40.         ans += a[i];
    41.     }
    42.     for(int l = 1; l <= n; l ++){
    43.         init();
    44.         add(a[l]);
    45.         for(int r = l + 1;r <= n; r ++){
    46.             add(a[r]);
    47.             if((r - l + 1) % 2){
    48.                 ans -= q2.top();
    49.             }
    50.         }
    51.     }
    52.     printf ("%lld\n",ans);
    53. }