洛谷P1133教主的花园题解

       通往题目的大门

       进入正题&＃xff0c;需要求最大观赏价值&＃xff0c;那么用于dp的f数组首先肯定要有两维&＃xff0c;第一维i表示第i个位置&＃xff0c;第二维j表示种第j种树&＃xff08;我们不妨设10,20,30这三种树为1,2,3&＃xff09;&＃xff0c;然后又发现&＃xff0c;第i个位置能种什么树&＃xff0c;不单单跟上一个位置有关&＃xff0c;还跟上上个位置有关&＃xff0c;那这样调用两位去dp显得十分复杂&＃xff0c;于是我们再开一维&＃xff0c;表示这个位置的树比上一个位置的树要高还是要低&＃xff08;0表示低&＃xff0c;1表示高&＃xff09;&＃xff0c;于是&＃xff0c;我们就可以写出dp方程&＃xff1a;

f[i][1][0]&＃61;maxx(f[i-1][2][1],f[i-1][3][1])&＃43;a[i].x;//第i个位置种第1种树&＃xff0c;那么它肯定比上一棵树要矮&＃xff0c;所以第3维是0&＃xff0c;于是看上一棵树&＃xff08;第i-1棵&＃xff09;是2还是3&＃xff0c;因为第i-1棵比第i棵树要高&＃xff0c;那么他一定也比第i-2棵树要高&＃xff0c;所以他们的第3维都是1&＃xff0c;记得后面还要加上当前这棵树的贡献
f[i][2][0]&＃61;f[i-1][3][1]&＃43;a[i].y;//如果种2并且小于前一种&＃xff0c;那前一种只能种3
f[i][2][1]&＃61;f[i-1][1][0]&＃43;a[i].y;//下面这两行类似
f[i][3][1]&＃61;maxx(f[i-1][1][0],f[i-1][2][0])&＃43;a[i].z;

       做完了&＃xff1f;不存在的。&＃xff08;告诉你们个大幂幂这个做法在洛谷上70分&＃xff09;

       仔细想想&＃xff0c;发现这个做法只能满足线型地种树&＃xff0c;也就是一排种过去&＃xff0c;但是&＃xff0c;题目要求是环形&＃xff0c;也就是说&＃xff0c;我们需要处理头和尾的问题&＃xff0c;所以&＃xff0c;我们再加一维&＃xff0c;表示第一个位置种的是什么树。

       可以发现&＃xff0c;第3~n-1个位置种什么树跟第一个位置种什么树然而并没有什么关系&＃xff0c;只要保证他们第四维相等就可以照常转移了&＃xff0c;于是我们稍稍修改一下上面的代码&＃xff0c;加上第四维&＃xff0c;就得出这样一个东西&＃xff1a;

for(int j&＃61;1;j<&＃61;3;j&＃43;&＃43;)
{f[i][1][0][j]&＃61;maxx(f[i-1][2][1][j],f[i-1][3][1][j])&＃43;a[i].x;f[i][2][0][j]&＃61;f[i-1][3][1][j]&＃43;a[i].y;f[i][2][1][j]&＃61;f[i-1][1][0][j]&＃43;a[i].y;f[i][3][1][j]&＃61;maxx(f[i-1][1][0][j],f[i-1][2][0][j])&＃43;a[i].z;
}

       代码的核心部分就是这样了&＃xff0c;然后再初始化一下第一位

       初始化第一个位置&＃xff1a;

f[1][1][0][1]&＃61;a[1].x;//注意第2维一定和第4维是一样的&＃xff0c;这段初始化也没啥不好理解的&＃xff0c;注释就不打啦
f[1][2][0][2]&＃61;a[1].y&＃xff1b;
f[1][2][1][2]&＃61;a[1].y;
f[1][3][1][3]&＃61;a[1].z;

        总体代码&＃xff1a;

#include
#include int f[100010][4][2][4];
struct node{int x,y,z;};
node a[100010];
int n;
inline int maxx(int x,int y){return x>y?x:y;}int main()
{scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);f[1][1][0][1]&＃61;a[1].x;f[1][2][0][2]&＃61;a[1].y;f[1][2][1][2]&＃61;a[1].y;f[1][3][1][3]&＃61;a[1].z;for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;3;j&＃43;&＃43;){f[i][1][0][j]&＃61;maxx(f[i-1][2][1][j],f[i-1][3][1][j])&＃43;a[i].x;f[i][2][0][j]&＃61;f[i-1][3][1][j]&＃43;a[i].y;f[i][2][1][j]&＃61;f[i-1][1][0][j]&＃43;a[i].y;f[i][3][1][j]&＃61;maxx(f[i-1][1][0][j],f[i-1][2][0][j])&＃43;a[i].z;}}printf("%d",maxx(maxx(maxx(maxx(maxx(f[n][1][0][2],f[n][1][0][3]),f[n][2][0][3]),f[n][2][1][1]),f[n][3][1][1]),f[n][3][1][2]));//最后从所有可能的情况中选择最大值输出
}