DP算法

DP(动态规划算法初步)

情形一 题目来源(http://acm.hdu.edu.cn/showproblem.php?pid=1003) 题面大概意思就是要找到最大和的子数列，并且输出其和，其起始索引+1,其终止索引+1 做这道题时，我一开始的思路是 直接暴力遍历找到所求解 上代码

#define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; int p[100005]; int main() { int T; scanf("%d", &T); for (int i = 0; i < T; i++) { int N; scanf("%d", &N); for (int j = 0; j < N; j++) { scanf("%d", &p[j]); } int sum = INT_MIN; int begin = 0, end = 0; for (int k = 0; k < N; k++) { int tmp = 0; for (int t = k; t < N; t++) { tmp += p[t]; if (tmp > sum) { sum = tmp; begin = k; end = t; } } } cout << "Case " << i + 1 << ":" << endl; cout << sum << " " << begin + 1 << " " << end + 1 << endl; if (i != T - 1)cout << endl; } return 0; }

代码提交后，果然WA 感觉应该是超时了，整个程序时间复杂度快有O(n^3)了，哎，不超时才怪

Solution

baidu了下人家的代码，看了一下人家的思路分析 假设有n个数，p1,p2…pn 用数学归纳法 那么 以p1为结尾的子数列有{p1} 以p2为结尾的子数列有{p1+p2,p2} 以p3为结尾的子数列有{p1+p2+p3,p2+p3,p3} … 以此类推 则该问题简化成求n组子数列中n个子子数列中的最大值 我用dp[]表示 对于p1:dp1=p1; 对于p2:dp2=max(p1+p2,p2)=max(dp1,p2); 对于p3:dp3=max(p1+p2+p3,p2+p3,p3)=max(dp2,p3); … 对于pn:dpn=max(dpn-1,pn); 由此 问题得解 上AC代码

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int p[100005]; int main() { int T; scanf("%d", &T); for (int lp = 0; lp < T; lp++) { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &p[i]); } int dp = p[0]; int max = dp; int begin = 0, end = 0; for (int j = 1; j < N; j++) { dp = (dp + p[j]) > p[j] ? (dp + p[j]) : p[j]; if (dp > max) { max = dp; end = j; } } int tmp = 0; for (int k = end; k >= 0; k--) { tmp += p[k]; if (tmp == max) { begin = k; } } cout << "Case " << lp + 1 << ":" << endl; cout << max << " " << begin+1 << " " << end+1 << endl; if (lp != T - 1)cout << endl; } return 0; }

这道题 我其实提交了挺多遍的，每次都没发现那个坑在哪 最后一次 哎 傻了 题目要求是在两个输出结果之间再endl一下，没说在每个结果endl啊

情形二 题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1087 题目大意是找到所给序列中递增子序列的最大和 与情形一不同，该题并未要求序列连续，但是核心算法与上题无差 首先建立一个dp[]数组,p[]为输入数据的数组 dp[0]=p[0] 一系列操作后，得到n个dp，最后直接sort就OK，输出dp数组中最后一个元素 核心代码

memset(dp, 0, sizeof(dp)); int sum = INT_MIN; for (int j = 0; j < n; j++) { dp[j] = p[j]; for (int k = 0; k <= j; k++) { if (p[k] < p[j]) { dp[j] = dp[j] > (dp[k] + p[j]) ? dp[j] : (dp[k] + p[j]); } } } sort(dp, dp + n); cout << dp[n - 1] << endl;

上述两种题型应该属于DP入门级别了，继续加油