hdu4374 單調隊列優化dp

hdu4374 單調隊列優化dp

 

題意就不多說了，直接說思路吧；

對每一層的點都有兩種方式到達（左邊不超過T步 或右邊不超過T步） 對這兩種方式容易得出

 

dp[i][j] = max( dp[i][j] , dp[i - 1][k] + sum[i][j] - sum[i][k - 1] ) ; //從上層的k向右走過來 dp[i][j] = max( dp[i][j] , dp[i - 1][k] + sum[i][k] - sum[i][j - 1] ) ; //從上層的k點向左走來

 

因為每一層的sum是定的 所以 只要求滿足條件的dp【i-1】【k】-sum[i][k-1]的最大值就行 這就用到單調隊列來優化了

 

 

#include
#include
#include
using namespace std;

#define INF -0x3f3f3f3f

int sum[20100],num[110][20100],id[20100],dp[110][20100],map[10010];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,m,i,j,x,T;
    while(~scanf("%d%d%d%d",&n,&m,&x,&T))
    {
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&num[i][j]);
            dp[i][j]=INF;
        }
        dp[1][x]=num[1][x];
        for(i=x-1;i>=1&&x-i<=T;i--)
        dp[1][i]=dp[1][i+1]+num[1][i];
        for(i=x+1;i<=m&&i-x<=T;i++)
        dp[1][i]=dp[1][i-1]+num[1][i];
        int front,top;
        sum[0]=0;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            sum[j]=sum[j-1]+num[i][j];
            front=0,top=0;
            for(j=1;j<=m;j++)
            {
                int tt=dp[i-1][j]-sum[j-1];
                while(front<top&&tt>map[top])
                top--;
                id[++top]=j;
                map[top]=tt;
                while(j-T>id[front+1]&&front<top)
                front++;
                dp[i][j]=max(dp[i][j],map[front+1]+sum[j]);    
            }
            front=0,top=0;
            sum[m+1]=0;
            for(j=m;j>=1;j--)
            sum[j]=sum[j+1]+num[i][j];
            for(j=m;j>=1;j--)
            {
                int tt=dp[i-1][j]-sum[j+1];
                while(front<top&&tt>map[top])
                top--;
                id[++top]=j;
                map[top]=tt;
                while(front<top&&id[front+1]>j+T)
                front++;
                dp[i][j]=max(dp[i][j],map[front+1]+sum[j]);
            }
        }
        int Max=INF;
        for(i=1;i<=m;i++)
        if(dp[n][i]>Max) Max=dp[n][i];
        printf("%d\n",Max);
    }
    return 0;
}