pycharm网站开发实例,重庆泡沫字制作,dede视频网站,景德镇企业网站建设题目描述 教主有着一个环形的花园#xff0c;他想在花园周围均匀地种上n棵树#xff0c;但是教主花园的土壤很特别#xff0c;每个位置适合种的树都不一样#xff0c;一些树可能会因为不适合这个位置的土壤而损失观赏价值。 教主最喜欢 3种树#xff0c;这3种树的高度分别…题目描述 教主有着一个环形的花园他想在花园周围均匀地种上n棵树但是教主花园的土壤很特别每个位置适合种的树都不一样一些树可能会因为不适合这个位置的土壤而损失观赏价值。 教主最喜欢 3种树这3种树的高度分别为 10,20,30。教主希望这一圈树种得有层次感所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低并且在此条件下教主想要你设计出一套方案使得观赏价值之和最高。 输入输出格式 输入格式 第一行为一个正整数 n 表示需要种的树的棵树。 接下来 n 行每行 3 个不超过 10000的正整数 \[a_i,b_i,c_i\] 按顺时针顺序表示了第 i 个位置种高度为 10,20,30 的树能获得的观赏价值。 第 i个位置的树与第 i1 个位置的树相邻特别地第 1 个位置的树与第 n 个位置的树相邻。 输出格式 一个正整数为最大的观赏价值和。 输入输出样例 输入样例#1 4 1 3 2 3 1 2 3 1 2 3 1 2 输出样例#1 11 说明 【样例说明】 第 1 至 n 个位置分别种上高度为 20,10,30,10 的树价值最高。 【数据规模与约定】 对于 20%的数据有 n≤10 对于 40% 的数据有 n≤100 对于 60% 的数据有 n≤1000 对于 100% 的数据有 4≤n≤100000 并保证 n 一定为偶数。 Solution 这道题的思路蛮好想的,只是稍微多了一些限制条件.状态定义:\[f[i][j][k]\] 表示当前 i 这个点, i-1 的选择为 j , 然后 i 的选择为 k.状态转移 枚举当前这个的点的 j 和 k,然后判断 j 和 k 的大小关系. 如 : \[ f[i][j][k] \]其中 jk 则有前驱状态:\[f[i-1][1...j-1][j]\] 其他亦可依次类推. 但是需要注意最后一个节点和第一个节点的大小关系区分. 为此,我们可以直接枚举一重 head. 然后在里面循环的时候注意判断最后一个节点即可. 代码 #includebits/stdc.h
using namespace std;
const int maxn100008;
int f[maxn][4][4];
int c[maxn][4],n;
int ans-1,head;
int main()
{ios::sync_with_stdio(false);cinn;for(int i1;in;i)for(int j1;j3;j)cinc[i][j];for(head1;head3;head){memset(f,0,sizeof(f));f[2][head][1]c[1][head]c[2][1];f[2][head][2]c[1][head]c[2][2];f[2][head][3]c[1][head]c[2][3];for(int i3;in;i){for(int j1;j3;j)for(int k1;k3;k){if(jk)continue;else{if(in){if(khead)continue;if(jkkhead)continue;if(jkkhead)continue; }if(jk)for(int l1;lj;l)f[i][j][k]max(f[i][j][k],f[i-1][l][j]c[i][k]);elsefor(int lj1;l3;l)f[i][j][k]max(f[i][j][k],f[i-1][l][j]c[i][k]);}} }for(int i1;i3;i)for(int j1;j3;j)ansmax(f[n][i][j],ans);}coutansendl;return 0;
} 转载于:https://www.cnblogs.com/Kv-Stalin/p/9123197.html
