局域网建设网站工具,中文商城响应式html网站模板,南京建筑人才招聘网,网站后台登陆验证码不对经典的dp打家劫舍问题状态设计dp[i][0]#xff1a;在前i个店铺中选#xff0c;且不选第i家的最大和dp[i][1]#xff1a;在前i个店铺中选#xff0c;且选第i家的最大和状态转移dp[i][0] max(dp[i-1][1], dp[i-1][0];第i家店不选#xff0c;那么我们可以选第i-1个店 也可以…经典的dp打家劫舍问题状态设计dp[i][0]在前i个店铺中选且不选第i家的最大和dp[i][1]在前i个店铺中选且选第i家的最大和状态转移dp[i][0] max(dp[i-1][1], dp[i-1][0];第i家店不选那么我们可以选第i-1个店 也可以不选第i-1个店dp[i][1] dp[i-1][0] a[i]; 第i家店选那么我们第i-1个店一定不能选因为不能选相邻两个还要记得加上第i家店的价值初始化dp[1][0] 0dp[1][1] a[1]不懂得化可以再看一下 ⌈状态设计⌋ 答案max(dp[n][0], dp[n][1])代码//大盗阿福
#include iostream
#include cstringusing namespace std;const int N 100010;
int a[N], dp[N][1];int main() {int t;scanf (%d, t);while (t --) {/*状态设计dp[i][0/1] : 打劫前i个店铺可得的最大金额, 且不包含/包含第i个数字的最大值状态转移dp[i][0] max(dp[i-1][1], dp[i-1][0]);dp[i][1] dp[i-1][0] a[i];初始化dp[1][1] a[1];输出max(dp[n][0], dp[n][1]);*/int n;scanf (%d, n);for (int i 1; i n; i )scanf (%d, a[i]);dp[1][1] a[1];for (int i 2; i n; i )dp[i][0] max(dp[i - 1][1], dp[i - 1][0]), dp[i][1] dp[i - 1][0] a[i];printf (%d\n, max(dp[n][0], dp[n][1]));}return 0;
}
/*
【输入样例】
2
3
1 8 2
4
10 7 6 14
【输出样例】
8
24
*/原题链接信息学奥赛一本通C版在线评测系统 (ssoier.cn)
