[luogu] P2049 魔术棋子 线性DP

前言

这和背包没什么事吧hh 传送门 :

思路

一开始以为摘花生的那种题,结果发现是需要求出所有的路径方案,因为数据范围很小

所以我们可以采用 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]三层循环 来 d p dp dp

表示第 i i i行第 j j j列值为 k k k的可能是否存在

然后通过形如线性DP的那种状态转移即可

• f [ i ] [ j ] [ k ] = f [ i ] [ j ] [ ( w ∗ a [ i ] [ j ] ) % k ] f[i][j][k] = f[i][j][(w*a[i][j])\%k] f[i][j][k]=f[i][j][(w∗a[i][j])%k]
• f [ i ] [ j ] [ k ] = f [ i ] [ j ] [ ( w ∗ a [ i ] [ j ] ) % k ] f[i][j][k] = f[i][j][(w*a[i][j])\%k] f[i][j][k]=f[i][j][(w∗a[i][j])%k]

当且仅当他的上一层状态存在的情况下进行转移

CODE

const int N  = 110;
int n,m,k;
int f[N][N][N];
int a[N][N];

void solve()
{
	cin>>n>>m>>k;
	for(int i=1;ia[i][j];
		
	f[0][1][1] = 1;
	f[1][0][1] = 1;
	
	//状态转移的相当于模拟了
	
	//。。。如果可以转移过来那么 当前状态一定从上层状态转移
	for(int i=1;i