题目链接

https://ac.nowcoder.com/acm/contest/7412/I

解题思路

我的思路：

建立set容器dp[i][j]，存储的是位于(i,j)时所有不同的权值和。
访问到(i,j)位置时，遍历(i-1,j)位置所有不同的权值和，再遍历(i,j-1)位置的权值和，把他俩位置中的权值和逐个与(i,j)位置的权值相加取模并insert进dp[i][j]中。
我代码运行时间比较短的原因在于 if(dp[i][j].size()>=mod){cout<<mod<<endl;return 0;}，含义为如果在循环到(n,m)位置之前已经有某个位置所含的不同权值和个数比1e4+7大了，说明后面无论怎么加，怎么变，只要是由这个权值和个数大于1e4+7的位置转移过去的，必然个数都为1e4+7，而(n,m)位置必然由(i,j)转移得到，所以直接输出并return即可。（自认为灵魂所在！QWQ）

大佬思路：

dp[i][j][k]为bool数组，为1表示(i,j)位置权值和为k的情况存在，为0表示不存在。
枚举余数情况。
最终答案为dp[n][m][k]，k从0到mod-1遍历累加。
注意：bool数组，不是bool开不下

我的AC代码

//我的代码运行时间比较短
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e4+7;
const int N=105;
set<int> dp[N][N];
ll a[N][N];
int n,m;
int read(){
    int x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=read()%mod;
    for(int i=1;i<=n;i++) dp[i][0].insert(0);
    for(int j=1;j<=m;j++) dp[0][j].insert(0);
    dp[1][1].insert(a[1][1]);
    for(int i=1;i<=n;i++)    
        for(int j=1;j<=m;j++){
            if(i!=1)
                for(set<int>::iterator it=dp[i-1][j].begin();it!=dp[i-1][j].end();it++)
                    dp[i][j].insert((*it+a[i][j])%mod);
            if(j!=1)
                for(set<int>::iterator it=dp[i][j-1].begin();it!=dp[i][j-1].end();it++)
                    dp[i][j].insert((*it+a[i][j])%mod);
            if(dp[i][j].size()>=mod){cout<<mod<<endl;return 0;}
        }
    cout<<dp[n][m].size()<<endl;
} 

大佬AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e4+7;
const int N=110;
bool dp[N][N][11000];//bool！！！
int a[N][N];
int ans;
int n,m;
int read(){
    int x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=read()%mod;

    dp[1][1][a[1][1]]=1;
    for(int i=1;i<=n;i++)    
        for(int j=1;j<=m;j++){
            if(i==1&&j==1) continue;
            for(int k=0;k<mod;k++){
                dp[i][j][(a[i][j]+k)%mod] |= dp[i-1][j][k];
                dp[i][j][(a[i][j]+k)%mod] |= dp[i][j-1][k];
            }
        }


    for(int k=0;k<mod;k++)
        ans+=dp[n][m][k];
    cout<<ans<<endl;
}