阿青的博客 这是注释，耶！

Jun 10 学习笔记

10 Jun 2018

学习笔记

UVa 10271

题目

刘汝佳请了K个客人到他家吃晚饭，加上他的家人：他的老婆、儿子、女儿、妈妈、爸爸、岳父、岳母，那么这顿晚饭一共有K+8个人。因为是吃中餐，所以需要筷子，他家里一共有N根筷子，而且长短不一，这时刘汝佳的ACMer本性又暴露出来了，他不按照正常的每个人都给两只筷子，而是每个人分3根筷子，其中最长的一根用来叉比较大块的食物，而另外两根较短的筷子当作正常的使用。为了让每个人用得更加舒服，显然，要让短的两根筷子长度尽量接近,设这三根筷子的长度为A, B, C(A <= B <= C)，那么较小两根会有一个平方差(A - B)^ 2。刘老师要你帮他算，怎样分配，所有人的平方差之和最小？

思路

考虑一道比较简单的问题：所有人从总数为N的筷子中各选取两根，使得每人手中筷子长度的平方差最小。此题可以通过设定f[i][j]表示前j人分配前i根筷子时最小的平方和，从前到后进行状态转移即可。

f[i][j] = min(f[i-1][j], f[i-2][j-1] + (len[i] - len[i - 1]) ^ 2)

对于本题，因为每个人需要三双筷子，无法使用从小到大的枚举方法，否则编号为i的筷子不会参与平方差的计算（它是长度最长的那一根筷子）。对于这一点，只需要将从小到大改为从大到小(i : N -> 1)进行计算即可，重写状态转移方程，得到

f[i][j] = min(f[i + 1][j], f[i + 2][j - 1]) + (len[i] - len[i + 1]) ^ 2)

此时因为不知道还是否有多余的筷子作为筷子组合中的C，需要保证(n - i - 1)[还剩下的筷子总数] - (j - 1) * 3 >= 1，即剩下j - 1人分配完后还有至少一根筷子。

代码

#include <iostream>
#include <stdio.h>
#include <cstring>
#define SQ(x) ((x)*(x))  

using namespace std;

typedef long long int64;  
const int INF = 0x3f3f3f3f;  

const int MAXN = 5100;  
int n, m;  
int len[MAXN];  
int f[MAXN][1010];  

int main() {
    int nCase;  
    scanf("%d", &nCase);  
    while (nCase--) {  
        scanf("%d%d", &m, &n);  
        for (int i = 1; i <= n; ++i)  
            scanf("%d", &len[i]);  
        m += 8;

        memset(f, INF, sizeof(f));
        for(int i = 0; i <= n; ++i) f[i][0] = 0;

        for (int i = n - 2; i >= 1; --i) {
            for (int j = m; j >= 1; --j) {
                f[i][j] = f[i + 1][j];
                if (f[i+2][j-1] != INF && (n-i-1)-(j-1)*3 >= 1)  
                    f[i][j] = min(f[i+1][j], f[i+2][j-1] + SQ(len[i] - len[i+1]));  
            }  
        }
    }
}

01背包

因为太简单就不写有的没的了

代码

    #include <stdio.h>
    #include <cstring>
    #include <algorithm>

    using namespace std;

    const int maxn = 100;
    const int maxc = 10000;
    int v[maxn], w[maxn];

    int main() {
    int n, V;
    int f[maxc];
    memset(f, 0, sizeof(f));
    scanf("%d%d", &n, &V);
    for(int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        scanf("%d", &w[i]);
    }
    for(int i = 0; i < n; i++) {
        for(int j = V; j >= 0; j--) {
            if(j >= w[i])
                f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    printf("%d", f[V]);
    }