洛谷 P3800 排序+DP

这题刚开始想练一练单调队列优化DP，但由于本人太菜，实在是搞不定，就换了个思路来写这道题。

把所有有power的点排序，然后遍历点，对于每个点，枚举前面的能到这个点的点，从中取最大的就🆗

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

struct node
{
    int x,y,z;
}t[5010];

int n,m,k,ti;
int f[5010],ans;

bool cmp(node k,node l)
{
    return k.x < l.x;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&ti);
    for(int i = 0;i < k; ++i)
        scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].z);
    sort(t,t + k,cmp);
    ans = 0;
    memset(f,0,sizeof(f));
    for(int i = 0;i < k; ++i)
    {
        f[i] = t[i].z;
        for(int j = 0;j < i; ++j)
        {
            if(abs(t[i].y - t[j].y) <= ti * abs(t[i].x - t[j].x))
                f[i] = max(f[i],f[j] + t[i].z);
        }
        ans = max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}

后来做了一下洛谷P1886，稍微懂了一丢丢，也贴一个代码吧（纪念自己在这个题上WA了这么多次）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int n,k,tot,x;
int l,r,q[1000100],a[1000100];
int ans[1000100];

int main()
{
    scanf("%d%d",&n,&k);
    tot = 0;
    l = 1; r = 1;
    for(int i = 1;i <= n; ++i) scanf("%d",&a[i]);
    q[1] = a[1];
    for(int i = 1;i <= n; ++i)
    {
        while(l <= r && q[r] >= a[i] && r) r--;
        q[++r] = a[i];
        if(i >= k)
        {
            if(a[i - k] == q[l]) l++;
             ans[++tot] = q[l];
        }
    }
    for(int i = 1;i <= tot; ++i)
    {
        printf("%d",ans[i]);
        if(i != tot) printf(" ");
            else printf("\n");
    }
    tot = 0;
    memset(q,0,sizeof(q));
    l = 1; r = 1;
    q[1] = a[1];
    for(int i = 1;i <= n; ++i)
    {
        while(l <= r && q[r] <= a[i]) r--;
        q[++r] = a[i];
        if(i >= k)
        {
            if(a[i - k] == q[l]) l++;
            ans[++tot] = q[l];
        }

    }
    for(int i = 1;i <= tot; ++i)
    {
        printf("%d",ans[i]);
        if(i != tot) printf(" ");
            else printf("\n");
    }
    return 0;
}

其实刚开始想的是N*M*T肯定TLE，就套用单调队列优化DP的式子看了一下觉得可以用这个省掉T那一维，但是理解不深实在考虑不出如何实现，，，做完1886这个题好像稍微懂一点了，ennnn 趁热打铁，我再去看看这个题

哈哈，我又回来了，终于看懂了，不容易啊。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int n,m,k,t,x,y,ans;
int l,r;
int a[5010][5010];
int q[5010][2];   //q[][0]存储数据，q[][1]存储位置用以判断是否在符合条件的区间
int dp[5010][5010];

int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i = 1;i <= k; ++i)
    {
        scanf("%d%d",&x,&y);
        scanf("%d",&a[x][y]);
    }
    for(int i = 1;i <= n; ++i)
    {
        l = 1; r = 0;
        for(int j = 1;j <= min(m,t); ++j)  
        {
            while(l <= r && q[r][0] <= dp[i - 1][j]) r--;
            q[++r][0] = dp[i - 1][j];
            q[r][1] = j;
        }
        for(int j = 1;j <= m; ++j)
        {
            if(j + t <= m)  
            {
                while(l <= r && q[r][0] <= dp[i - 1][j + t]) r--;
                q[++r][0] = dp[i - 1][j + t];
                q[r][1] = j + t;
            }
            if(q[l][1] < j - t) l++;   //判断是否在符合条件的区间
            dp[i][j] = q[l][0] + a[i][j];
        }
    }
    ans = 0;
    for(int i = 1;i <= m; ++i) ans = max(ans,dp[n][i]);
    printf("%d\n",ans);
    return 0;
}