首页 > 代码库 > Gym - 101128E Wooden Signs DP
Gym - 101128E Wooden Signs DP
题目大意：
一共n块木板，前两个数给出最底下木块的两个端点，后面n-1个数给出第i层的一个固定端点，问你木块的所有放置情况。
分析：
状态：
d[i][j]表示第i个木块，第i-1块木板的未固定端点为j的所有方案数
状态转移：
如果a[i]<=min(j,a[i-1)，也就是说固定的那一点在i-1块木板的两个端点的左侧，那么只能有一种情况。d[i][r]=(d[i][r]+d[i-1][j])%mod;
同理，如果a[i]>= max(j,a[i-1)。d[i][l]=(d[i][l]+d[i-1][j])%mod;
如果在中间，那么以上两种情况都要算上
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=2147483647;const int maxn=2000+5;int n,a[maxn];ll d[maxn][maxn];int main(){ while(~scanf("%d",&n)) { for(int i=0; i<=n; i++) scanf("%d",&a[i]); memset(d,0,sizeof(d)); d[1][a[0]]=1; for(int i=2; i<=n; i++) { for(int j=1; j<=n+1; j++) { int l=min(j,a[i-1]); int r=max(j,a[i-1]); if(a[i]<=l) d[i][r]=(d[i][r]+d[i-1][j])%mod; else if(a[i]>=r) d[i][l]=(d[i][l]+d[i-1][j])%mod; else { d[i][r]=(d[i][r]+d[i-1][j])%mod; d[i][l]=(d[i][l]+d[i-1][j])%mod; } } } ll ans=0; for(int j=1; j<=n+1; j++) ans=(ans+d[n][j])%mod; printf("%I64d\n",ans); } return 0;}
Gym - 101128E Wooden Signs DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。