// 704 麦当劳.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/5/problem/251
喜欢吃麦当劳的蜗蜗要在学校呆 n
天,如果第 i
天蜗蜗吃到了麦当劳,他可以获得 ai
点快乐值。然而蜗蜗不能吃太多麦当劳,在连续的 m
天中,他最多只能有一半的天数吃麦当劳。请问蜗蜗在这 n
天中最多可以得到多少快乐值?
输入格式
第一行两个整数 n,m。
第二行 n 个整数 a1,a2,...,an。
输出格式
一行一个整数表示答案。
样例输入
4 3
1 2 9 4
样例输出
5
数据范围
对于 100%
的数据,保证 2≤n≤100000,2≤m≤8,1≤ai≤10000
8 8
6808 5250 74 3659 8931 1273 7545 879
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int a[N];
long long pre[1 << 8];
long long curr[1 << 8];
int n, m;
bool check(int st) {
int cnt = 0;
while (st) {
if (st & 1) cnt++;
st >>= 1;
}
if (cnt <= m / 2) return true;
return false;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i < (1<<8); i++) {
pre[i] = -999999999999999;
curr[i] = -999999999999999;
}
pre[0] = 0;
long long ans = 0;
for (int i = 1; i <= n; i++) {
int f = 0;
for (int st = 0; st <( 1 << m); st++) {
int currst = st / 2;
if(pre[st]>=0)
curr[currst] = max(pre[st] , curr[currst]);
if (check(currst + (1 << (m-1))) ) {
curr[currst + (1 << (m-1))] = max(curr[currst + (1 << (m - 1))], pre[st] + a[i]);
}
if(i==n)
ans =max(ans, max(curr[currst], curr[currst + (1 << (m - 1))]));
}
swap(pre,curr);
}
cout << ans << endl;
return 0;
}
标签:int,currst,样例,麦当劳,天中,251
From: https://www.cnblogs.com/itdef/p/18534833