<commit_before>---
layout:     post
title:      "Codeforces 627F Group Projects(动态规划)"
subtitle:   "Dynamic programming"
description: "Codeforces 627F DP"
date:       2016-03-10 11:00:00
author:     "Scalpel"
header-img: "img/home-bg-o.jpg"
tags:
- 题解
- 动态规划
- Codeforces
---
[题目链接](http://codeforces.com/problemset/problem/626/F)  
**题意**：  
有n个人完成一项团队项目，第i个人可花费ai时间独立完成自己的一份工作，把n个人划分成多组，定义每组的imbalance为其中的最大值减最小值，求有多少种分组方案使各组的imbalance之和最多为k。   
**思路**：  
首先对ai排序，然后利用动态规划来做。设`dp[i][j][t]`为考虑了i个人，有j个组是开放的（只有ai的最小值，没有最大值，组内还可以继续加人），imbalance之和为t。对第i个人有四种转移：  
1、第i个人自己单独一个非开放的组；   
2、第i个人进入j个开放的组中的某一个； 
3、第i个人作为某个开放的组的最大值，从而关闭这个组。     
4、第i个人新开一个开放的组；  
其中第i个人对imbalance之和的增加量为`j*(a[i]-a[i-1])` *这个地方想了好久才明白，加第i个人时，只会对当前开放的j个组有影响，因为其他的最大值已经确定，对于每个开放的组，我们可以将它们的最值都增加a[i]-a[i-1]，这样可以得到a[i]，并且相当于虚拟的把a[i]放进各组中，最后可以确定各组的最大值。*  
可以用滚动数组减少空间占用。  

~~~cpp
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define FIO ios::sync_with_stdio(false); cin.tie(nullptr);
const int MOD = 1000000007;

long long dp[2][201][1001];
int main() 
{
    FIO
    int n, k;
    cin >> n >> k;
    int a[201] = {0};
    for (int i = 1; i <= n; ++i) 
        cin >> a[i];<commit_msg>revise code<commit_after>---
layout:     post
title:      "Codeforces 627F Group Projects(动态规划)"
subtitle:   "Dynamic programming"
description: "Codeforces 627F DP"
date:       2016-03-10 11:00:00
author:     "Scalpel"
header-img: "img/home-bg-o.jpg"
tags:
- 题解
- 动态规划
- Codeforces
---
[题目链接](http://codeforces.com/problemset/problem/626/F)  
**题意**：  
有n个人完成一项团队项目，第i个人可花费ai时间独立完成自己的一份工作，把n个人划分成多组，定义每组的imbalance为其中的最大值减最小值，求有多少种分组方案使各组的imbalance之和最多为k。   
**思路**：  
首先对ai排序，然后利用动态规划来做。设`dp[i][j][t]`为考虑了i个人，有j个组是开放的（只有ai的最小值，没有最大值，组内还可以继续加人），imbalance之和为t。对第i个人有四种转移：  
1、第i个人自己单独一个非开放的组；   
2、第i个人进入j个开放的组中的某一个； 
3、第i个人作为某个开放的组的最大值，从而关闭这个组。     
4、第i个人新开一个开放的组；  
其中第i个人对imbalance之和的增加量为`j*(a[i]-a[i-1])` *这个地方想了好久才明白，加第i个人时，只会对当前开放的j个组有影响，因为其他的最大值已经确定，对于每个开放的组，我们可以将它们的最值都增加a[i]-a[i-1]，这样可以得到a[i]，并且相当于虚拟的把a[i]放进各组中，最后可以确定各组的最大值。*  
可以用滚动数组减少空间占用。  

~~~cpp
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
const int MOD = 1000000007;

long long dp[2][201][1001];
int main() 
{
    FIO
    int n, k;
    cin >> n >> k;
    int a[201] = {0};
    for (int i = 1; i <= n; ++i) 
        cin >> a[i];
{'fraction_non_alphanumeric': 0.1589293182768716, 'fraction_numerical': 0.043496445002091176, 'mean_word_length': 4.9502487562189055, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6189346', 'n_tokens_mistral': 1537, 'n_tokens_neox': 1608, 'n_words': 160}