外包的工作值得做吗,seo营销推广全程实例,徐州房产网,南京设计网页公司三倍经验
题目描述
数字金字塔由 n n n 行整数组成#xff0c;第 i ( 1 ≤ i ≤ n ) i(1\le i\le n) i(1≤i≤n) 行有 i i i 个数字#xff0c;一个示例如下。 73 98 1 02 7 4 4
4 5 2 6 5现在你在金字塔的顶部#xff08;第一行#xff09;第 i ( 1 ≤ i ≤ n ) i(1\le i\le n) i(1≤i≤n) 行有 i i i 个数字一个示例如下。 73 98 1 02 7 4 4
4 5 2 6 5现在你在金字塔的顶部第一行你希望走到金字塔的底部第 n n n 行每一步你只能走向当前所在位置的左下方的数字或者右下方的数字。同时作为一个强大的小朋友你可以选择金字塔中的不多于 k k k 个数字让他们成为原来的 3 3 3 倍。
你会收集你路上经过的所有位置上的数字最后的得分即为收集的数字之和求最大得分。
输入格式
第一行输入两个整数 n , k n,k n,k表示数字金字塔的行数和乘 3 3 3 的数字个数最大值 接下来 n n n 行其中的第 i i i 行有 i i i 个以空格隔开的整数依次表示数字金字塔第 i i i 行的数字 a i , 1 , a i , 2 , a i , 3 . . . a i , i a_{i,1},a_{i,2},a_{i,3}...a_{i,i} ai,1,ai,2,ai,3...ai,i。
输出格式
一行一个整数表示最大得分。
样例 #1
样例输入 #1
5 3
7
3 9
8 1 0
2 7 4 4
4 5 2 6 5样例输出 #1
75提示
对于 30 % 30\% 30% 的数据满足 k ≤ n ≤ 6 k\le n\le 6 k≤n≤6并且对于任意 1 ≤ i ≤ n 1\le i\le n 1≤i≤n 1 ≤ j ≤ i 1\le j\le i 1≤j≤i 满足 0 ≤ a i , j ≤ 100 0\le a_{i,j}\le 100 0≤ai,j≤100 对于 100 % 100\% 100% 的数据满足 1 ≤ n ≤ 100 1\le n\le100 1≤n≤100 0 ≤ k ≤ n ( n 1 ) 2 0\le k\le \dfrac{n(n1)}{2} 0≤k≤2n(n1)且对于任意 1 ≤ i ≤ n 1\le i\le n 1≤i≤n 1 ≤ j ≤ i 1\le j\le i 1≤j≤i 满足 ∣ a i , j ∣ ≤ 1 0 9 |a_{i,j}|\le 10^9 ∣ai,j∣≤109。 首先可以知道这道题和dp三角形模型有点关系所以我们可以先知道对于三角形模型的状态转移是由左下和右下的最大值转移过来。
但是对于这道题给我们加入了一个条件也就是我们能任选k个数进行乘三操作这时候会有两个想法。
第一个想法是按照之前的方法进行搜索并且记录下路径对路径上最大的三个数进行乘三操作当然这个想法是错误的。
第二个想法是给dp数组多加一个维度这里可以这样理解对于要乘的k个数我们其实很难进行搜索出来所以我们就可以多加一个维度来代表这个数是乘三还是不乘三这样就能够使用dp数组表示出来这个情况。
那么这时候就可以得到f[i][j][times]代表在点 ( i , j ) (i,j) (i,j)并且剩余乘三次数为 t i m e s times times次的情况下能够得到的最大的数值。
然后再进行记忆化搜索就很容易了但是这里要注意一个小点原题给出的三角形中的数据是有可能为负数的所以我们要把dp数组初始化为负无穷这个时候我们就必须要多设立一个判重数组进行判重了。
#include bits/stdc.h
using namespace std;
const int N 110;
const int mod 1e9 7;
const int Mod 1e9 7;
#define int long longint n,k;
int g[N][N];
int f[N][N][N];
bool vis[N][N][N];int dfs(int i,int j,int times){if(vis[i][j][times])return f[i][j][times];vis[i][j][times] 1;if(i n){if(times){f[i][j][times] max(g[i][j],g[i][j]*3);}else f[i][j][times] g[i][j];return f[i][j][times];}if(times){f[i][j][times] max(f[i][j][times],dfs(i1,j1,times - 1) g[i][j]*3);f[i][j][times] max(f[i][j][times],dfs(i1,j,times - 1) g[i][j]*3);}f[i][j][times] max(f[i][j][times],dfs(i1,j1,times) g[i][j]);f[i][j][times] max(f[i][j][times],dfs(i1,j,times) g[i][j]);return f[i][j][times];
}void solve(int times)
{cin n k;memset(f,-0x3f,sizeof f);for(int i 1;i n;i){for(int j 1;j i;j){cin g[i][j];}}dfs(1,1,k);int ans f[1][1][k];cout ans endl;
}signed main()
{int T;// cin T;T 1;for (int i 1; i T; i){solve(i);}return 0;
}
