11.14日志

1.Problem - D - Codeforces

考试时很快想到要用到二分答案但是在写check函数的时候没有想到贪心思路的错误导致没有赛时ac,我原来的思路是根据每次二分的mid来约束每一段区间的和不能超过mid从而来一起约束删除数字的和,双指针就能够实现这个方法,可是这是已经默认了我们不删除第一个数字,若是我们删除第一个数字有没有可能会更优呢,以此类推如果我们删除第一第二会不会更优,于是发现好像不能贪心得出,考虑dp,我们令dpi表示前i个数字并且删除第i个数字时的最小值,那么怎么转移呢,删除第i个数之前是一段长度未知的区间,dpi得从这段区间中的最小值转移过来,既然如此考虑单调队列dp,我们的

dp[i] = dp[j](sum(a[j] ~ a[i - 1]) <= mid) + a[i]

那么我们的队列里面装的就是所有左端点为a[i-1]的总和<=mid的区间，因为这是单调队列,我们维护的是一个单调递增的队列因此队首是最优的转移对象,所以i直接从队首转移即可,需要注意的是我们不能直接返回dp[n] <= mid,因为这默认了我们要删除第n个数所以我们要返回dp[n + 1] <= mid

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<int , string> pis;
const int N = 1e6 + 10,M = 2e5 + 5e4,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;

int n;
ll a[N],b[N];

bool check(ll mid)
{
    vector <ll> dp(n + 2 , 0),q(n + 2 , 0);
    int tt = -1,hh = 0;
    q[++tt] = 0;
    for(int i = 1 ; i <= n + 1 ; i++)
    {
        while(tt >= hh && b[i - 1] - b[q[hh]] > mid)
        {
            hh++;
        }
        dp[i] = dp[q[hh]] + a[i];
        while(tt >= hh && dp[q[tt]] >= dp[i])
        {
            tt--;
        }
        q[++tt] = i;
    }

    return dp[n + 1] <= mid;
}

void work()
{
    cin>>n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin>>a[i];
        b[i] = a[i] + b[i - 1];
    }  
    a[n + 1] = 0;      
    
    check(7);
    
    ll l = 0,r = 1e18;
    while(l < r)
    {
        ll mid = (l + r) / 2;
        if(check(mid))
        {
            r = mid;
        }else
        {
            l = mid + 1;
        }
    }

    cout<<r<<"\n";
}

int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
        
    int t;
    cin>>t;

    while(t--)
    {
        work();
    }
}

// 5
// 2 4 10 4 8


// 5
// 2 4 10 4 8

2.P2034 选择数字 - 洛谷 | 计算机科学教育新生态

和上一题很像,这题我们需要一点逆向的思维,虽然他让我们求的是选择的数字的最大和,但是不好处理,所以我们要对不选的数字和进行dp,我们的dpi表示的是前i个数字中且第i个数字不选的不选的数字的最小和,对于i不选它转移的区间是什么呢,我们发现第i个不选那么上一个不选的区间其实是[i - k - 1 ~ i - 1],并且我们求的是minn因此我们维护的应该是一个单调递减的单调队列,每次由队头进行转移

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<int , string> pis;
const int N = 1e6 + 10,M = 2e5 + 5e4,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;

int n,k;
ll a[N],b[N],dp[N];     //前i个数中第i个数不选的不选的数的最小和 
int q[N],tt = -1,hh = 0;

int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
        
    cin>>n>>k;
    for(int i = 1 ; i <= n ; i++)
    {
        cin>>a[i];
        b[i] = b[i - 1] + a[i];
    }    
    
    q[++tt] = 0;
    for(int i = 1 ; i <= n + 1 ; i++)
    {
        while(hh <= tt && q[hh] < i - k - 1)
        {
            hh++;
        }
        dp[i] = dp[q[hh]] + a[i];
        while(hh <= tt && dp[q[tt]] >= dp[i])
        {
            tt--;
        }
        q[++tt] = i;
    }

    cout<<b[n] - dp[n + 1];
}