【01背包dp+思维】吉林大学ACM集训队选拔赛（重现赛）B-Subset of Five

传送门
题意：给定n个数，求使得若干数之和模5==0&&使得和最大,输出那个最大和
基本的思路就是拿dp做，不过它可以正向做一波，也可以反向做一波，下面来分别介绍一下
解题思路1:dp[i][j]就表示前i项中若干项和模5等于j的最大和的值，明显最后dp[n][0]就是答案，每个数都有选和不选两种方案，明显是个01背包，不过核心部位需要一个小小的处理，请看下面的图和解释

Code：

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<stack>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9+7;
typedef long long ll;
typedef unsigned long long ull;
int n;
int a[maxn];
ll dp[maxn][5];
int main(){
    ll sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    if(sum%5==0)
        printf("%lld\n",sum);///总和恰好是5的倍数，直接输出
    else{
        memset(dp,-0x3f,sizeof dp);///这里的初始化必须将数组开始设为无穷小，不然样例都过不去，
        ///有可能a[i]是一个很大的数，这就使得刚开始计算就会出错
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=4;j++)
            {
                int flag=a[i]%5;
                if(j-flag>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-flag]+a[i]);
                else dp[i][j]=max(dp[i-1][j],dp[i-1][j+5-flag]+a[i]);
            }
        }
        printf("%lld",dp[n][0]);
    }
    return 0;
}

解题思路2：假设所有数的和为sum，我们可以找出其中若干项的和sum1使得sum1%5=sum%5并且sum1最小，这就使得(sum-sum1)%5==0&&sum最大，此时dp[i][j]表示前i项中若干项的和模5等于j的最小和，明显最后的答案就是sum-sum1，也就是sum-dp[i][sum%5],核心和上面是一致的
Code:

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<stack>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9+7;
typedef long long ll;
typedef unsigned long long ull;
int n;
int a[maxn];
ll dp[maxn][6];
int main(){
    ll sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    if(sum%5==0)
        printf("%lld\n",sum);
    else{
        memset(dp,0x3f,sizeof dp);///和正向做正好相反，初始化为无穷大
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=4;j++)
            {
                int flag=a[i]%5;
                if(j-flag>=0) dp[i][j]=min(dp[i-1][j],dp[i-1][j-flag]+a[i]);
                else dp[i][j]=min(dp[i-1][j],dp[i-1][j+5-flag]+a[i]);
            }
        }
        printf("%lld",sum-dp[n][sum%5]);
    }
    return 0;
}

万事尽可期待! ! !