題目鏈接：地宮取寶
解題思路：動態規劃，在每一個位置的狀態考慮，當前這個位置的狀態是由哪些狀態轉移過來的，
dp[i][j][u][v]表示在(i,j)這個位置，拿到u個物品，且這些物品的最大價值是v，
我們可以考慮當前位置(i,j)拿不拿當前這個物品，如果不拿那么可以從dp[i-1][j][u][v]、dp[i][j-1][u][v]轉移過來，表示上一個位置已經拿到了u個物品最大價值為v的，如果拿則可以從dp[i-1][j][u-1][c]、dp[i][j-1][u-1][c]轉移過來，表示上一個位置拿了u-1個，并且最大價值為c(c為小于v的數)，最后再把最后手上可能拿的價值的方案數加起來即可，
ps：因為這道題的所有物品價值范圍是0…120…12，可以把他們全部都遞增，范圍就變成了1…131…13，因為我們記錄的是方案數，只關心各個物品之間的大小關系，具體數值不影響答案，但是這樣的做法可以把00作為一個特殊邊界來處理
#include<bits/stdc++.h>
#define x first
#define y second
#define mem(h) memset(h,-1,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
inline LL read(){
LL o=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
return o*f;
}
}using namespace IO;
//#############以上是自定義技巧（可忽略）##########
const int N=50+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e9+7,P=131;
int dp[N][N][13][14];
int n,m,k;
int w[N][N];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
w[i][j]++;//這里是需要注意的點，把所有的權值+1，更好處理也不影響結果
}
}
dp[1][1][1][w[1][1]]=1;//如果拿起(1,1)的物品
dp[1][1][0][0]=1;//如果不拿
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==1&&j==1)continue;//這個位置可以跳過
for(int u=0;u<=k;u++){//列舉到達當前位置可能拿了幾個物品
for(int v=0;v<=13;v++){//列舉到達當前位置手中的最大物品價值
int &val=dp[i][j][u][v];
val=(val+dp[i-1][j][u][v])%mod;//不拿當前位置的物品時可能從這些狀態轉移過來
val=(val+dp[i][j-1][u][v])%mod;
if(u>0&&v==w[i][j]){//如果到達當前位置手中有物品，并且物品最大價值等于當前位置的物品價值，那么可以拿起當前物品
for(int c=0;c<v;c++){//可以從這些狀態轉移過來
val=(val+dp[i-1][j][u-1][c])%mod;
val=(val+dp[i][j-1][u-1][c])%mod;
}
}
}
}
}
}
int res=0;
for(int i=0;i<=13;i++){
res=(res+dp[n][m][k][i])%mod;//把最后手上可能拿的最大價值方案數相加
}
cout<<res<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/167060.html
標籤：其他