NC25088. [USACO 2006 Oct S]Corn Fields
描述
输入描述
Line 1: two space-separated integers M and N
Lines 2.. M+1: row I +1 describes each cell in row I of the ranch, N space-separated integers indicating whether the cell can be planted (1 means fertile and suitable for planting, 0 means barren and not suitable for planting).
输出描述
Line 1: an integer: FJ total number of alternatives divided by a remainder of 100,000,000.
示例1
输入:
2 3 1 1 1 0 1 0
输出:
9
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2019-06-23 15:46:53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e8,ans,dp[15][1<<12]={1};
int n,m,sta[15],t,p;
vector<int>ve[15];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&t);
if(t)sta[j]|=1<<(i-1);
}
ve[0].push_back(0);
for(int i=1;i<=m;i++){
ve[i].push_back(0);
for(int s=sta[i];s;s=(s-1)&sta[i])
if((s&(s<<1))==0)
ve[i].push_back(s);
}
for(int i=1;i<=m;i++){
for(int j=0;j<ve[i-1].size();j++){
t=ve[i-1][j];
for(int k=0;k<ve[i].size();k++){
p=ve[i][k];
if((t&p)==0)dp[i][p]=(dp[i][p]+dp[i-1][t])%mod;
}
}
}
for(int i=0;i<ve[m].size();i++){
t=ve[m][i];
if(dp[m][t])ans=(ans+dp[m][t])%mod;
}
printf("%lld\n",ans);
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 940K, 提交时间: 2023-08-12 18:25:05
#include<bits/stdc++.h>
using namespace std;
const int mod=100000000;
int m,n,t,a[20],x,dp[15][1<<13];
int main()
{
cin>>m>>n;
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>x;
a[i]=(a[i]<<1)+x;
}
}
dp[0][0]=1;
int len=(1<<n);
for(int i=1;i<=m;i++){
// cout<<"Y";
for(int s=0;s<len;s++){
if((a[i]|s)!=a[i]||(s&(s>>1))!=0)continue;
for(int t=0;t<len;t++){
if((s&t)==0){
dp[i][s]+=dp[i-1][t];
}
}
}
}
int ans=0;
for(int i=0;i<len;i++){
ans=ans+dp[m][i];
ans%=mod;
}
cout<<ans;
return 0;
}