定制家具网站建设,网页网站开发项目设计,wordpress表单微信,北京工程建设公共资源交易平台1.股票买卖 一、贪心 考虑一种方案#xff0c;在每次上升的前一天购入股票#xff0c;并在上升后的当天卖出的方案
if (w[i] w[i - 1])res w[i] - w[i - 1];接下来证明该贪心思路得出的方案即是最优解。 #xff08;1#xff09;证明贪心解 ≥ 最优解#xff1a; …
1.股票买卖 一、贪心 考虑一种方案在每次上升的前一天购入股票并在上升后的当天卖出的方案
if (w[i] w[i - 1])res w[i] - w[i - 1];接下来证明该贪心思路得出的方案即是最优解。 1证明贪心解 ≥ 最优解 由于贪心解都是取区间长度为 1 的解因此假设存在于最优解中的某个区间 [i,j] 的长度 1
那么会出现一下三种情况
对应三种情形最优解选取的区间最终点位于上方、下方、相等。
对于情形一显然 最优解 贪心解 对于情形二显然 最优解 贪心解 对于情形三毫无疑问这就是存在于贪心解中的情形因此 贪心解 最优解 得证
2证明贪心解 ≤最优解 这部分无需证明因为贪心解即是合法解所以他的方案必定大于等于最优解
#include iostream
using namespace std;
const int N 1e5 10;
int n;
int w[N];int main() {scanf(%d, n);for (int i 1; i n; i) scanf(%d, w[i]);int res 0;for (int i 2; i n 1; i) {if (w[i] - w[i - 1] 0) res w[i] - w[i - 1];}printf(%d\n, res);return 0;
}
二、闫氏DP分析法 具体的状态机模型分析如下图: 一共只2有种状态:
1. 当前处于未持股状态0 对应可以进行的转换 0-0 不买入继续观望那么就什么都不发生 0-1 买入股票那么收益就要减去当前市场的股票价格 2. 当前处于持股状态1 对应可以进行的转换 1-1 不卖出继续观望那么就什么都不发生 1-0 卖出股票那么收益就要加上当前市场的股票价格 #include iostream
using namespace std;
const int N 1e5 10, INF 0x3f3f3f3f;
int n;
int w[N];
int f[N][2];int main() {scanf(%d, n);for (int i 1; i n; i) scanf(%d, w[i]);f[0][1] -INF;for (int i 1; i n; i) {f[i][0] max(f[i - 1][0], f[i - 1][1] w[i]);f[i][1] max(f[i - 1][1], f[i - 1][0] - w[i]);}printf(%d\n, f[n][0]);return 0;
}
2.货舱选址 #include iostream
#include cstring
#include algorithm
using namespace std;
const int N 100010;
int n;
int a[N];
int main () {scanf (%d,n);for (int i 1;i n;i) scanf (%d,a[i]);sort (a 1,a 1 n);int ans 0;for (int i 1,j n;i j;i,j--) ans a[j] - a[i];printf (%d\n,ans);return 0;
}3.糖果传递
