题解
2024-08-05 08:40:20
发布于:上海
24阅读
0回复
0点赞
一个比较基本的动态规划,寻找不同路径的数量(就是数据一言难尽)
#include<iostream>
using namespace std;
const int N=1001,MOD=114514;
long long dp[N];//一个比较基本的动态规划,就是“不同的路径”这种题目升级版
//dp[i]表示从1走到i的方案数
//使用标数法轻松解决
int n,k,e;
int main(){
dp[1]=1;//起始点只有一种走法(不走)能够到达,所以赋值为1
cin>>n;
for(int i=1;i<=n;i++){
cin>>k;
for(int j=1;j<=k;j++){
cin>>e;
dp[e]=(dp[i]+dp[e])%MOD;//这个终点能够通过现在的起点到达
//所以是由起点的方案数加上现在该终点已有的方案数得到
}
}
cout<<dp[n];
return 0;
}
这里空空如也
有帮助,赞一个