本文主要是介绍P1622 释放囚犯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LOG P1622 释放囚犯
传送门（洛谷）
题目描述：
输入数据：
20 3
3 6 14
输出数据：
35分析：
容易看出，每次给犯人吃肉都是一个区间，则很容易得出此题为一个区间动归
区间动归的一般模板：f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+…)
这里的f[i][j]是表示放出i号到j号的犯人最少给的肉，而我们找中介点k的时候，是已经将i,j号的犯人放出了的，则有k号没有放出，所以最终的转移方程应是这个区间的人数减去自己，则为:
f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[j+1]-a[i-1]-1-1);
可以动手画一下图
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define don(i,a,b) for(register int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int maxn=1e6+10;
const int maxm=1e3+10;
int n,m;
int a[maxn],f[maxm][maxm];template <class t> inline void read(t &x)
{int f=1;x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}x*=f;
}
/*--------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------*/void readdata()
{read(n),read(m);rep(i,1,m) read(a[i]);
}void work()
{sort(a+1,a+1+m);a[0]=0;a[m+1]=n+1;rep(l,1,m) {for(register int i=1;i+l-1<=m;i++) {int j=i+l-1;f[i][j]=INT_MAX;for(register int k=i;k<=j;k++)f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[j+1]-a[i-1]-1-1);}}printf("%d\n",f[1][m]);
}int main()
{freopen("input.txt","r",stdin);readdata();work();return 0;
}
给出记忆化搜索版的：
枚举区间人数 l , r l,r l,r
用 l o w e r b o u n d 和 u p p e r b o u n d lower_~bound和upper~bound lower bound和upper bound找出在这个区间中有多少个可以放的人
解释为什么 u p p e r b o u n d ( a + 1 , a + m + 1 , r ) − a − 1 upper ~bound(a+1,a+m+1,r)-a-1 upper bound(a+1,a+m+1,r)−a−1
我们是在找区间 l − r l-r l−r的小于 r r r的数，如果用 u p p e r b o u n d upper~bound upper bound则可能不存在，移到后面一下标，因此超出了 r r r的范围
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define don(i,a,b) for(register int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int maxn=1e6+10;
const int maxm=1e3+10;
int n,m;
int a[maxn],f[maxm][maxm];template <class t> inline void read(t &x)
{int f=1;x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}x*=f;
}
/*--------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------*/void readdata()
{read(n),read(m);rep(i,1,m) read(a[i]);
}inline int dfs(int l,int r) {if(f[l][r]!=-1) return f[l][r];if(l>r) return 0;int x=lower_bound(a+1,a+1+m,l)-a;int y=upper_bound(a+1,a+1+m,r)-a-1;if(x>y) return 0;f[l][r]=INT_MAX;rep(i,x,y) f[l][r]=min(f[l][r],dfs(l,a[i]-1)+dfs(a[i]+1,r)+r-l);return f[l][r];
}void work()
{sort(a+1,a+1+m);memset(f,-1,sizeof(f));a[0]=0;a[m+1]=n+1;printf("%d\n",dfs(1,n));
}int main()
{freopen("input.txt","r",stdin);readdata();work();return 0;
}
这篇关于P1622 释放囚犯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
