F. Zero Remainder Sum（四维dp）

今天药忘吃喽~ 2021-07-17 00:07 292阅读 0赞

[题目][Link 1]

状态：dp\[i\]\[j\]\[k\]\[o\] 代表第i行前j个数已经选定k个数余o最大总和的值

首先来单独看一行，lst\[i\]\[j\] 代表第i行第j个数

dp\[i\]\[j\]\[k\]\[o\]=dp\[i\]\[j-1\]\[k\]\[o\] , 此代表在第i行我们不选第j个数，所以选定的个数k不变，余数也不变

dp\[i\]\[j\]\[k\]\[o\]=dp\[i\]\[j-1\]\[k-1\]\[(o-lst\[i\]\[j\]+70*p)%p\] ，此代表第i行选择了第j个数，所以由选定数k-1转换而来，p是题目要求余的数，o-lst\[i\]\[j\]表示，要想得到加了lst\[i\]\[j\]从而得到o的余数那么之前的余数得是o-lst\[i\]\[j\]，加上70*p防止是一个负数。

在以上过程需遍历完i,j,k,o，每一种情况都需要推导过去。

那么如何进行一行行的推导？

我们要求的结果是总的余p的最大和，其实只需要把每一行前m个数的余数对应的最大和赋给下一行作为开始的dp\[i+1\]\[0\]\[0\]\[o\]即可，将上一行的总的最优状态用下一行的还没选定的初始状态全部存储转化，继续进行后面的推导，而最终的答案就等于dp\[n+1\]\[0\]\[0\]\[0\]\[0\],代表了在最后余0时 前面所有状态不断推导得出的最优余0的最大总和。

Code:

#include<iostream>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    int dp[75][75][75][75];//dp[i][j][k][o]在第i行前j个数选定k个余o的最大值
    int lst[100][100];
    
    int main()
    { 
    	FAST;
    	int n, m, p;cin >> n >> m >> p;
    	memset(dp, 128, sizeof(dp));//127最大128最小因为memset是按4位4位赋值的
    	dp[1][0][0][0] = 0;
    	for (int i = 1;i <= n;i++)for (int j = 1;j <= m;j++)cin >> lst[i][j];
    	for (int i = 1;i <= n;i++)
    	{ 
    		for (int j = 1;j <= m;j++)
    		{ 
    			for (int k = 0;k <= min(j,m / 2);k++)
    			{ 
    				for (int o = 0;o <= p - 1;o++)
    				{ 
    					dp[i][j][k][o] = max(dp[i][j][k][o], dp[i][j - 1][k][o]);
    
    					if (k)	dp[i][j][k][o] = max(dp[i][j][k][o], dp[i][j - 1][k - 1][(o - lst[i][j] + p * 70) % p]+lst[i][j]);
    				}
    				for (int o = 0;o <= p-1;o++)	dp[i + 1][0][0][o] = max(dp[i + 1][0][0][o], dp[i][j][k][o]);
    			}
    		}
    	}
    	cout << dp[n + 1][0][0][0] << endl;
    }

[Link 1]: https://codeforc.es/problemset/problem/1433/F