工作(job)
【题目描述】
老板娘很讨厌工作,但老板一定要她工作。
现在有连续\(n\)天,老板娘需要分配她的工作时间。
在第\(i\)天工作每小时需要消耗\(a_i\)的精力,老板娘希望合理分配自己的工
作时间使自己消耗尽量少的精力。
但老板又不希望老板娘摸鱼,所以他要求老板娘对于任意的连续7天她
工作的总时间都不能少于7小时。
因为工作的特殊性,老板娘只能在每天分配整数小时的工作时间(当然
能为0)。
【输入格式】
从job.in中读入数据。
第一行一个整数\(T\)表示数据组数。
每组数据第一行一个整数\(n\)表示连续的天数。
接下里有\(n\)个整数,
【输出格式】
将答案输出到job.out。
输出老板娘最少消耗多少精力。
【样例输入】
1 10 1 6 3 2 4 5 2 1 2 7 3
【样例输出】
14
【样例解释】
(3,0,0,2,0,0,2,3,0,0)安排即可。
【数据规模与约定】
对于 30%的数据,7 ≤\(n\)≤ 10
对于 60%的数据,7 ≤\(n\)≤ 100
对于 100%的数据,7 ≤\(n\)≤ 10000, \(T\)≤ 100
题解:
这个题是7天工作7小时,因为我们找的是最少消耗的精力数量,
那么我们可以从七天里边找一个最少的一天来干7天活,然后
每七天找一天,这样我们就可以求出最少解了
code:
#include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <vector> #include <cstdio> #include <string> #include <cstring> #include <iomanip> #include <cstdlib> #include <iostream> #include <algorithm> #define N 10010 #define M 1010 #define int long long using namespace std; int t, n, num[N]; int f[N]; int read() { int s = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); return f ? -s : s; } signed main() { t = read(); while (t--) { memset(f, 63, sizeof(f)); n = read(); for (int i = 1; i <= n; i++) num[i] = read(); for (int i = 1; i <= 7; i++) f[i] = 7 * num[i]; for (int i = 8; i <= n; i++) { for (int j = 1; j <= 7; j++) f[i] = min(f[i - j], f[i]); f[i] += 7 * num[i]; } int minn = 1e18; for (int i = 0; i <= 6; i++) minn = min (minn, f[n - i]); cout << minn << "\n"; } return 0; }