首页 > > 程序设计 > C/C++ >

One hundred layer HDU - 4374

2018-06-17 21:41:21来源：未知阅读 ()

$sum[i][j][k]$表示第i层第j到k列的和

$ans[i][j]$表示第i层最终停留在第j列的最大值，那么显然$ans[i][j]=max(ans[i-1][j-t]+sum[i][j-t][j],..,ans[i-1][j+t]+sum[i][j+t][j])$

显然，直接按照方程做，时间复杂度$O(nmt)$，是无法通过的。但是看到max，可以想到用一些RMQ的方法优化。

这里重要的是一个分解（未想到）：

$ans1[i][j]$表示第i层下来后向右走并停留在第j列的最大值

$ans2[i][j]$表示第i层下来后向左走并停留在第j列的最大值

求出每一行的ans1和ans2后，那么$ans[i][j]=max(ans1[i][j],ans2[i][j])$

那么：（为了方便，a[j]表示第i行第j列）

$ans1[i][j]=max(ans[i-1][j]+a[j],..,ans[i-1][j-t]+a[j]+...+a[j-t])$

$ans2[i][j]=max(ans[i-1][j]+a[j],..,ans[i-1][j+t]+a[j]+..+a[j+t])$

还要做一些处理：（貌似别人的代码都是直接上啊？难道状态没定义好？）

对于ans1：

t=2时，

$$\begin{equation}\begin{split}ans1[i][1]&=max(ans[i-1][1]+a[1])\\
&=max(ans[i-1][1])+a[1]\end{split}\end{equation}$$
$$\begin{equation}\begin{split}ans1[i][2]&=max(ans[i-1][1]+a[1]+a[2],ans[i-1][2]+a[2])\\
&=max(ans[i-1][1],ans[i-1][2]-a[1])+a[1]+a[2]\end{split}\end{equation}$$
...

对于ans2：

t=1

$$\begin{equation}\begin{split}ans2[i][m]&=max(ans[i-1][m]+a[m])\\&=max(ans[i-1][m])+a[m]\end{split}\end{equation}$$
$$\begin{equation}\begin{split}ans2[i][m-1]&=max(ans[i-1][m-1]+a[m-1],ans[i-1][m]+a[m]+a[m-1])\\&=max(ans[i-1][m],ans[i-1][m-1]-a[m])+a[m]+a[m-1]\end{split}\end{equation}$$
$$\begin{equation}\begin{split}ans[i][m-2]&=max(ans[i-1][m-2]+a[m-2],ans[i-1][m-1]+a[m-2]+a[m-1])\\&=max(ans[i-1][m-2]-a[m]-a[m-1],ans[i-1][m-1]-a[m])+a[m]+a[m-1]+a[m-2]\end{split}\end{equation}$$
.....

这样，优化的方法就比较明显了，用一个单调队列维护滑动窗口的最小值即可。

错误次数：很多

查错时间：>1小时

错误原因：63行数组名打错，ans2打成ans1，单调队列复制粘贴时未修改

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<set>
 5 using namespace std;
 6 typedef pair<int,int> P;
 7 int l,r,n,m,x,y,a[105][10010],ans[105][10010],ans1[105][10010],ans2[105][10010],sum[10010];
 8 int anss;
 9 P q[10010],t;
10 int main()
11 {
12     int i,j;
13     while(scanf("%d%d%d%d",&n,&m,&x,&y)==4)
14     {
15         anss=-0x3f3f3f3f;
16         memset(ans,140,sizeof(ans));
17         for(i=1;i<=n;i++)
18             for(j=1;j<=m;j++)
19                 scanf("%d",&a[i][j]);
20         ans[1][x]=a[1][x];
21         for(i=1;i<=y;i++)
22         {
23             if(x+i<=m)    ans[1][x+i]=ans[1][x+i-1]+a[1][x+i];
24             if(x-i>=1)    ans[1][x-i]=ans[1][x-i+1]+a[1][x-i];
25         }
26         for(i=2;i<=n;i++)
27         {
28             for(j=1;j<=m;j++)
29                 sum[j]=sum[j-1]+a[i][j];
30             l=r=0;
31             for(j=1;j<=y+1;j++)
32             {
33                 t=P(ans[i-1][j]-sum[j-1],j);
34                 while(l<r&&q[r-1].first<=t.first)    --r;
35                 q[r++]=t;
36                 ans1[i][j]=q[l].first+sum[j];
37             }
38             for(j=y+2;j<=m;j++)
39             {
40                 if(l<r&&q[l].second<j-y)    l++;
41                 t=P(ans[i-1][j]-sum[j-1],j);
42                 while(l<r&&q[r-1].first<=t.first)    --r;
43                 q[r++]=t;
44                 ans1[i][j]=q[l].first+sum[j];
45             }
46             sum[m+1]=0;
47             for(j=m;j>=1;j--)
48                 sum[j]=sum[j+1]+a[i][j];
49             l=r=0;
50             for(j=m;j>=m-y;j--)
51             {
52                 t=P(ans[i-1][j]-sum[j+1],j);
53                 while(l<r&&q[r-1].first<=t.first)    --r;
54                 q[r++]=t;
55                 ans2[i][j]=q[l].first+sum[j];
56             }
57             for(j=m-y-1;j>=1;j--)
58             {
59                 if(l<r&&q[l].second>j+y)    l++;
60                 t=P(ans[i-1][j]-sum[j+1],j);
61                 while(l<r&&q[r-1].first<=t.first)    --r;
62                 q[r++]=t;
63                 ans2[i][j]=q[l].first+sum[j];
64             }
65             for(j=1;j<=m;j++)
66                 ans[i][j]=max(ans1[i][j],ans2[i][j]);
67         }
68         for(j=1;j<=m;j++)
69             anss=max(anss,ans[n][j]);
70         printf("%d\n",anss);
71     }
72     return 0;
73 }

sum[i][j]表示第i层第j到k列的和
ans[i][j]表示第i层停留在第j列的最大值
ans[i][j]=max(ans[i-1][j-t]+sum[i][j-t][j],..,ans[i-1][j+t]+sum[i][j+t][j])

**分解：
ans1[i][j]表示第i层下来后向右走并停留在第j列的最大值
ans2..左..
ans1[i][j]=max(ans[i-1][j]+sum[i][j][j],..,ans[i-1][j-t]+sum[i][j-t][j])
t=2
ans1[i][1]=max(ans[i-1][1]+a[1])
=max(ans[i-1][1])+a[1]
ans1[i][2]=max(ans[i-1][1]+a[1]+a[2],ans[i-1][2]+a[2])
=max(ans[i-1][1],ans[i-1][2]-a[1])+a[1]+a[2]
//=max(ans[i-1][1]+a[1],ans[i-1][2])+a[2]
//=max(ans1[i][1],ans[i-1][2])+a[2]

ans1[i][3]=max(ans[i-1][1]+a[1]+a[2]+a[3],ans[i-1][2]+a[2]+a[3],ans[i-1][3]+a[3])
=max(ans[i-1][1],ans[i-1][2]-a[1],ans[i-1][3]-a[1]-a[2])+a[1]+a[2]+a[3]
//=max(ans[i-1][1]+a[1]+a[2],ans[i-1][2]+a[2],ans[i-1][3])+a[3]
//=max(ans1[i][2],ans[i-1][3])+a[3]

ans1[i][4]=max(ans[i-1][2]+a[2]+a[3]+a[4],ans[i-1][3]+a[3]+a[4],ans[i-1][4]+a[4])
=max(ans[i-1][2]-a[1],ans[i-1][3]-a[1]-a[2],ans[i-1][4]-a[1]-a[2]-a[3])+a[1]+a[2]+a[3]+a[4]
//=max(ans[i-1][2]+a[2]+a[3],ans[i-1][3]+a[3],ans[i-1][4])+a[4]

ans2[i][j]=max(ans[i-1][j]+a[j],ans[i-1][j+1]+a[j]+a[j+1],..,ans[i-1][j+t]+a[j]+..+a[j+t])
t=1
ans2[i][m]=max(ans[i-1][m]+a[m])
=max(ans[i-1][m])+a[m]
ans2[i][m-1]=max(ans[i-1][m-1]+a[m-1],ans[i-1][m]+a[m]+a[m-1])
=max(ans[i-1][m],ans[i-1][m-1]-a[m])+a[m]+a[m-1]
ans[i][m-2]=max(ans[i-1][m-2]+a[m-2],ans[i-1][m-1]+a[m-2]+a[m-1])
=max(ans[i-1][m-2]-a[m]-a[m-1],ans[i-1][m-1]-a[m])+a[m]+a[m-1]+a[m-2]

6 3 2 2
7 8 1 7 8 1
4 5 6 4 5 6
1 2 3 1 2 3

t=1
ans[2][1]=max(ans[1][1]+sum[2][1][1],ans[1][2]+sum[2][2][1])
ans[2][2]=max(ans[1][1]+sum[2][1][2],ans[1][2]+sum[2][2][2],ans[1][3]+sum[2][3][2])
ans[2][3]=max(ans[1][2]+sum[2][2][3],ans[1][3]+sum[2][3][3],ans[1][4]+sum[2][4][3])

t=2
ans[2][1]=max(ans[1][1]+sum[2][1][1],ans[1][2]+sum[2][1][2],ans[1][3]+sum[2][1][3])
ans[2][2]=max(ans[1][1]+sum[2][1][2],ans[1][2]+sum[2][2][2],ans[1][3]+sum[2][2][3],ans[1][4]+sum[2][2][4])
ans[2][3]=max(ans[1][1]+sum[2][1][3],ans[1][2]+sum[2][2][3],ans[1][3]+sum[2][3][3],ans[1][4]+sum[2][3][4],ans[1][5]+sum[2][3][5])
ans[2][4]=max(ans[1][2]+sum[2][2][4],ans[1][3]+sum[2][3][4],ans[1][4]+sum[2][4][4],ans[1][5]+sum[2][4][5],ans[1][6]+sum[2][4][6])

t=2
ans[2][1]=max(ans[1][1]+a[2][1], ans[1][2]+a[2][1]+a[2][2], ans[1][3]+a[2][1]+a[2][2]+a[2][3])
ans[2][2]=max(ans[1][1]+a[2][1]+a[2][2], ans[1][2]+a[2][2], ans[1][3]+a[2][2]+a[2][3], ans[1][4]+a[2][2]+a[2][3]+a[2][4])
ans[2][3]=max(ans[1][1]+a[2][1]+a[2][2]+a[2][3],ans[1][2]+a[2][2]+a[2][3], ans[1][3]+a[2][3], ans[1][4]+a[2][3]+a[2][4], ans[1][5]+a[2][3]+a[2][4]+a[2][5])
ans[2][4]=max(ans[1][2]+a[2][2]+a[2][3]+a[2][4],ans[1][3]+a[2][3]+a[2][4], ans[1][4]+a[2][4], ans[1][5]+a[2][4]+a[2][5], ans[1][6]+a[2][4]+a[2][5]+a[2][6])

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有