CF1433 F - Zero Remainder Sum(分组背包,余数分组)

  • 时间:
  • 来源:互联网
  • 文章标签:

传送门
按照题目的意思,我们可以把每一行看成一组,然后把每一行处理出来当做分组背包来做,但如果直接暴力去做的话值域太大,所以我们可以按照这题的特性,因为k很小,所以我们按照余数来区分这些值域,处理好每一行的复杂度是(35×70×70×35),之后的分组背包dp复杂度是(70×70×70),足以过这题.

#define LL long long
#define pq priority_queue
#define ULL unsigned long long
#define pb push_back
#define mem(a,x) memset(a,x,sizeof a)
#define pii pair<int,int>
#define fir(i,a,b) for(int i=a;i<=(int)b;++i)
#define afir(i,a,b) for(int i=(int)a;i>=b;--i)
#define ft first
#define vi vector<int>
#define sd second
#define ALL(a) a.begin(),a.end()
#define bug puts("-------")
#define mpr(a,b) make_pair(a,b)
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5+10;
const int M = 70*35;
const int INF = 0x8f8f8f8f;
inline void read(int &a){
    int x = 0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    a = x*f;
}

int a[90],dp[4910],bag[75][75],f[4910],dpp[75][75];
int num,nn,m,kk;
int maxsum(int row){
    mem(dp,0);
    mem(f,0x3f);
    dp[0] = 1;
    f[0] = 0;
    fir(i,1,m){
        afir(j,M,a[i]){
            if(!dp[j] && dp[j-a[i]] && f[j-a[i]] < num){
                dp[j] = 1;
                f[j] = f[j-a[i]] + 1;
            }
            else if(dp[j])
                f[j] = min(f[j],f[j-a[i]]+1);
        }
    }
    fir(i,1,4900)
        if(dp[i])
            bag[row][i%kk] = i;

    return 0;
}
int main(){

    int n;
    cin >> n >> m >> kk;
    num = m/2;
    int ans = 0;
    mem(bag,0x8f);
    fir(i,1,n){
        fir(j,1,m)
            cin >> a[j];
        maxsum(i);
    }
    mem(dpp,0x8f);
    dpp[0][0] = 0;
    fir(i,1,n){
        fir(j,0,kk-1){
            dpp[i][j] = dpp[i-1][j];
            fir(k,0,kk-1){
                if(bag[i][(k-j+kk)%kk] == INF) continue;
                dpp[i][j] = max(dpp[i][j],dpp[i-1][k]+bag[i][(k-j+kk)%kk]);
            }
        }
    }
    fir(i,1,n) ans = max(ans,dpp[i][0]);
    cout << ans;
    
    return 0;
}    

本文链接http://www.taodudu.cc/news/show-1782071.html