DEF

背包

D - Jin Ge Jin Qu hao

题意：

• 在KTV还剩t秒钟的时间 你需要在n首歌中选择尽量多的歌使得歌的数量最多的前提下剩下的时间最小

解题思路：

• 因为要至少留一秒给金曲，所以时间是$t-1$，然后把时间看成总容量，把状态定义成恰好唱了当前时间的情况下的最大歌曲数，最后再从高到底遍历一遍就行了。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string.h>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int dp[N];
int a[N];
int main()
{
    int t;
    scanf("%d",&t);
    int tot=1;
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=m-1;j>=a[i];j--)
            {
                dp[j]=max(dp[j],dp[j-a[i]]+1);
            }
        }
        int ans=0,pos=0;
        for(int i=m-1;i>=0;i--)
        {
            if(dp[i]>ans)
            {
                ans=dp[i];
                pos=i;
            }
        }
        printf("Case %d: %d %d\n",tot++,ans+1,pos+678);
    }
    return 0;
}

E - Team Them Up!

题意：

• 有$n$个人，他们之间的关系有四种，给出一些关系$a$,$b$表示$b$知道$a$，现在想把这些人分成两组，每个组里面所有人都相互知道，如果可以分成这两组，找出两组人数相差最少的情况。

解题思路：

• 其实先开始想的是用并查集来表示，但是表示$a$、$b$互相知道的时候发现很麻烦，然后想到了用二分图去写，将互相认识的人连在一起，但是发现如果是这样的话要双向边才有用，所以正难则反就可以去建它的补图，将不认识的人连在一起，注意先要判断这个是不是二分图，用染色法即可，最后统计每个连通分量中的同色的个数（一共只有两个颜色也就是两个集合，问题就转化为从两个集合中选人分配到两个组中，是两个组的总合差最小）。

代码：

参考https://blog.csdn.net/u013007900/article/details/38512039。

F - Piggy-Bank

题意：

• 给定存钱罐的初始重量和最终重量，给定$n$中货币的价值，重量，求恰好满足存钱罐的最终重量的货币总钱数最小值，若不满足输出This is impossible.

解题思路：

• 因为每种货币可以放任意数量，所以这道题是完全背包的板子题，最后注意输出格式就行了。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string.h>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e4+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int dp[N];
int v[N],w[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        m-=n;
        int tt;
        scanf("%d",&tt);
        for(int i=0;i<tt;i++)
        {
            scanf("%d%d",&v[i],&w[i]);
        }
        memset(dp,inf,sizeof(dp));
        dp[0]=0;
        for(int i=0;i<tt;i++)
        {
            for(int j=w[i];j<=m;j++)
            {
                dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        if(dp[m]>=inf)
            printf("This is impossible.\n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]);
    }
    return 0;
}