政府网站如何建设管理/seo公司赚钱吗

Problem

codeforces.com/contest/779/problem/C

题意

有 n 个物品，每件今天 a 元，一周后 b 元。要全部都买，且今天至少买 k 个。问最小的花费。

Analysis

贪心。优先买 a <= b 的物品。如果必须买 a > b 的物品，那么优先选 a - b 比较小的那些（亏得少）。剩下的，几时便宜几时买。

起初想的是DP：dp[i][j][0/1]：前 i 件物品，今天买 j 件的最小花费（第三维 0 和 1 分别表示第 i 件今天不买（一周后买）、今天买）

状态转移：dp[i][j][0] = b[i] + min { dp[i-1][j][0] , dp[i-1][j][1] }

dp[i][j][1] = a[i] + min { dp[i-1][j-1][0] , dp[i-1][j-1][1] }

对每一个 i，初始化：dp[i][0][0] = Zigma { b[j] | 1<=j<=i }，dp[i][0][1] = INF（表示不可能）

最后答案是 min { dp[n][k~n][0~1] }。

实现时第一维用滚动数组。

然后超时了，因为复杂度是 O(n^2)，n = 2e5

不过这种写法不知道会不会对其它题有启发，备份一下。

Source code

Greedy

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200000;struct node
{int a, b;
} item[N];inline bool cmp(const node &a, const node &b)
{return a.b-a.a > b.b-b.a;
}int main()
{ios::sync_with_stdio(false);int n, k;cin >> n >> k;for(int i=0; i<n; ++i)cin >> item[i].a;for(int j=0; j<n; ++j)cin >> item[j].b;sort(item, item+n, cmp);int ans = 0;for(int i=0; i<k; ++i)ans += item[i].a;for(int i=k; i<n; ++i)ans += min(item[i].a, item[i].b);cout << ans << endl;return 0;
}

DP

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200000, BIG = 0x7f7f7f7f;int a[N+1], b[N+1], dp[2][N+1][2];int main()
{int n, k;scanf("%d%d", &n, &k);for(int i=1; i<=n; ++i)scanf("%d", a+i);for(int j=1; j<=n; ++j)scanf("%d", b+j);for(int i=0; i<2; ++i)for(int j=1; j<=n; ++j)dp[i][j][0] = dp[i][j][1] = BIG;dp[0][0][0] = 0;dp[0][0][1] = BIG;for(int i=1, cnt=0; i<=n; ++i){dp[i&1][0][0] = cnt += b[i];dp[i&1][0][1] = BIG;for(int j=1; j<=i; ++j){if(dp[i&1^1][j-1][0]!=BIG || dp[i&1^1][j-1][1]!=BIG)dp[i&1][j][1] = a[i] + min(dp[i&1^1][j-1][0],dp[i&1^1][j-1][1]);if(dp[i&1^1][j][0]!=BIG || dp[i&1^1][j][1]!=BIG)dp[i&1][j][0] = b[i] + min(dp[i&1^1][j][0],dp[i&1^1][j][1]);}}int ans = BIG;for(int i=k; i<=n; ++i)ans = min(ans, min(dp[n&1][i][0], dp[n&1][i][1]));printf("%d\n", ans);return 0;
}