本文主要是介绍SEERC 2018 I Inversion(dp or 记忆化搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/group/xrTA2IaQje/contest/254611/problem/I
题目大意：对一个1~n序列中，逆序的点连边，问能满足选中的点内部无边，但是外部的点至少与选中的点其中一个有边的边集数量
题目思路：
方法1：dp
首先先还原出序列，由于只有100个点，可以n^2暴力还原。用一个数组in记录入度，对于给出的边，使得所有的边都从大到小指，那么in[x]就表示x这个点前面应该有in[x]个数字比x大，那么从小往大放，初始的序列为1~n,如果in[x]=3，那么就从剩下的序列中，去掉前三个(因为再去多的话，后面比他小的数就不止三个，少的话又不够三个)，那么取出4，原序列变1~3,5~n，以此类推。
然后可以发现，符合要求的点其实就是序列中的上升子序列个数(一定要到不能拓展)，还原出原序列后就可以进行dp，对于一个点来说，一定要从比他小的点过来才能上升，但是同时又要满足这个比他小的点x和他y之间，不能有大于x小于y的数字，否则会出现重复计算，所以有一个maxx专门记末尾的值，倒退时一定是递增的。讲可能比较乱，直接看代码即可
方法2：记忆化搜索
这里再用一个新方法求序列：拓扑排序。按照优先级建边，对于提到的逆序的就直接逆序建边，没提到的就是正序建边，最后跑个拓扑排序，拓扑序就是要求的序列。
对于序列建图，可以发现可以连的边就是中间不能出现在两边之间的数，比如连1~4那么中间不能有2 3，那么题目等价于询问有多少路径满足起点入度为0，终点出度为0，记忆化搜索即可
以下是代码：
方法1：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 2e5+5;
const ll MOD =1e9+7;
ll n,m,x,y,in[MAXN],a[MAXN],vis[MAXN],dp[MAXN];
int main(){while(~scanf("%I64d%I64d",&n,&m)){memset(in,0,sizeof(in));memset(vis,0,sizeof(vis));rep(i,1,m){scanf("%I64d%I64d",&x,&y);if(x<y)swap(x,y);in[y]++;}rep(i,1,n){rep(j,1,n){if(vis[j])continue;if(in[i])in[i]--;else {a[i]=j;vis[j]=1;break;}}}rep(i,1,n){dp[i]=0;ll maxx=0;per(j,i-1,1){if(a[j]>a[i])continue;if(a[j]>maxx){maxx=a[j];dp[i]+=dp[j];}}dp[i]=max(dp[i],1ll);}ll ans=0,maxx=0;per(i,n,1){if(a[i]>maxx){maxx=a[i];ans+=dp[i];}}printf("%I64d\n",ans);}return 0;
}
方法2：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 100+5;
const ll MOD =1e9+7;
ll n,m,x,y,in[MAXN],a[MAXN],vis[MAXN][MAXN],dp[MAXN];
vector<ll>v[MAXN];
queue<ll>q;
ll dfs(ll x){if(dp[x]!=-1)return dp[x];dp[x]=0;int len=v[x].size();if(!len)dp[x]=1;rep(i,0,len-1){int y=v[x][i];dfs(y);dp[x]+=dp[y];}return dp[x];
}
int main(){while(~scanf("%I64d%I64d",&n,&m)){memset(vis,0,sizeof(vis));memset(dp,-1,sizeof(dp));memset(in,0,sizeof(in));rep(i,1,n)v[i].clear();rep(i,1,m){scanf("%I64d%I64d",&x,&y);if(x<y)swap(x,y);vis[x][y]=vis[y][x]=1;v[x].push_back(y);in[y]++;}rep(i,1,n){rep(j,i+1,n){if(vis[i][j])continue;v[i].push_back(j);in[j]++;}}rep(i,1,n){if(!in[i])q.push(i);}int cnt=0;while(!q.empty()){int x=q.front();q.pop();a[x]=++cnt;int len=v[x].size();rep(i,0,len-1){int y=v[x][i];in[y]--;if(!in[y])q.push(y);}}rep(i,1,n)v[i].clear(),in[i]=0;rep(i,1,n){rep(j,i+1,n){if(a[j]<a[i])continue;int flag=0;rep(k,i+1,j-1){if(a[k]>a[i]&&a[k]<a[j]){flag=1;break;}}if(!flag){v[i].push_back(j);in[j]++;}}}ll ans=0;rep(i,1,n){if(!in[i])ans+=dfs(i);}printf("%I64d\n",ans);}return 0;
}
这篇关于SEERC 2018 I Inversion(dp or 记忆化搜索)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
