【dp专题】NOIP真题-DP专题练习
这里学习一下DP的正确姿势。
也为了ZJOI2019去水一下做一些准备
题解就随便写写啦.
后续还是会有专题练习和综合练习的.
给出$n \times m$矩阵每次在每一行取n个数，一共取m次，
第i次取数的权值是$2^i$，给出一个取数的顺序，最大化取完所有数的贡献和。
输出贡献和。
对于100%的数据$1\leq n,m \leq 80,0<a_{i,j} \leq 10^3 $
需要使用高精度，考虑一个DP，$f[i][j][k]$表示第i行，共取j次，其中k次在前面，显然(j-k)在后面
第j次取数在前面取的那么$f[i][j][k]$是由$f[i][j-1][k-1]$转移而来，得dp方程$f[i][j][k]=f[i][j-1][k-1]+2^j \times a[k]$ (取的数在从左往右数第$k$个)
第j次取数在后面取的那么$f[i][j][k]$是由$f[i][j-1][k]$转移而来，得dp方程$f[i][j-1][k]+2^j \times a[m-(j-k)+1]$ （取的数在从左向右数第$m-(j-k)+1$个）
然后整理可得DP方程$f[i][j][k]=max{f[i][j-1][k-1]+2^j \times a[k] , f[i][j-1][k]+2^j \times a[m-(j-k)+1] }$
考虑边界条件对于$f[i][j][k]$是有意义的当且仅当$0 \leq j \leq k$，然后使用高精度计算(预处理2的幂的Lint数)
复杂度$O(km^3)$,其中k是高精度数的位数可视为常数
code：
# include <bits/stdc++.h>
# define fp(i,s,t) for(int i=s;i<=t;i++)
# define int long long
using namespace std;
const int N=;
const int L=;
char s[L];
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
struct Lint{
int len,num[L];
Lint () { len=; memset(num,,sizeof(num));}
Lint change(int x) {
Lint a;
if (x==) { a.num[]=;a.len=; return a;}
a.len=;
while (x>) a.num[++a.len]=x%,x/=;
return a;
}
void print(Lint x) {
for (int i=x.len;i>=;i--) putchar(x.num[i]+'');
putchar('\n');
}
Lint operator + (const Lint &t) const {
Lint ans;
memset(ans.num,,sizeof(ans.num));
ans.len=max(len,t.len);
for (int i=;i<=ans.len;i++) {
ans.num[i]+=num[i]+t.num[i];
ans.num[i+]+=ans.num[i]/;
ans.num[i]%=;
}
if (ans.num[ans.len+]>) ans.len++;
return ans;
}
Lint operator * (const Lint &t) const {
Lint ans;
for (int i=;i<=len;i++)
for (int j=;j<=t.len;j++)
ans.num[i+j-]+=num[i]*t.num[j];
for (int i=;i<=len+t.len;i++) {
ans.num[i+]+=ans.num[i]/;
ans.num[i]%=;
}
if (ans.num[len+t.len]>) ans.len=len+t.len;
else ans.len=len+t.len-;
return ans;
}
bool operator < (const Lint &t) const {
if (len>t.len) return false;
else if (len<t.len) return true;
for (int i=len;i>=;i--)
if (num[i]<t.num[i]) return true;
else if (num[i]>t.num[i]) return false;
return false;
}
}rd;
Lint Max(Lint x,Lint y){if (x<y) return y; else return x;}
int n,m;
Lint f[N][N],a[N][N],ans;
Lint pw[N];
signed main()
{
scanf("%lld%lld",&n,&m);
fp(i,,n) fp(j,,m) a[i][j]=rd.change(read());
pw[]=rd.change(); Lint num_2=rd.change();
fp(i,,m) pw[i]=pw[i-]*num_2;
fp(i,,n) {
Lint ret=rd.change(); memset(f,,sizeof(f));
fp(j,,m) fp(k,,j) {
if (k!=) f[j][k]=f[j-][k-]+pw[j]*a[i][k];
if (j->=k-) f[j][k]=max(f[j][k],f[j-][k]+pw[j]*a[i][m-j+k+]);
}
fp(k,,m) ret=Max(ret,f[m][k]);
ans=ans+ret;
}
rd.print(ans);
return ;
}
P1005 矩阵取数游戏
给出一个长度为m的字符串，和n个字典$S_i$ ，分成k份，每份里面单独处理，若一个位置为单词首字母可以在后匹配出一个字典，
那么有1的贡献，求出一个分配方案使得字符串分成k份后，贡献值最大。
对于100%的数据$1 \leq m,n \leq 200, 1 \leq k \leq 40 , 字典S_i\leq 6$
如果我们知道s的唯一连续划分[l,r]中总贡献是GetVal(l,r)，那么就是一个简单的动态规划问题了。
令$f[i][j]$表示前i个字母划分成j份，最大贡献，显然是一个位置k转移过来增加GetVal(k+1,i)这么多贡献
即$f[i][j]=max\{ f[k][j-1]+GetVal(k+1,i)\}$，然后考虑GetVal(l,r)的暴力求解，直接枚举每一位i属于[l,r]，然后枚举n个字典暴力匹配
注意判断是否超出r的右边界的限制，不要加进去。
然后如果枚举i的时候在线做GetVal会多个n的复杂度，不妨离线$O(n^3)$预处理出$val[l,r]=GetVal(l,r)$
然后$O(n^3)$的动态规划，显然是跑不满的。
# include <bits/stdc++.h>
using namespace std;
string s,th;
char mp[][];
int p,k,n,m;
int f[][],val[][];
bool check(int pos,int limt)
{
for (int i=;i<=n;i++) {
int l=strlen(mp[i]);
if (pos+l->limt||pos+l->m) continue;
bool flag=true;
for (int j=;j<l;j++)
if (s[pos+j]!=mp[i][j]) {
flag=false; break;
}
if (flag) return true;
}
return false;
}
int GetVal(int l,int r)
{
int ret=;
for (int i=l;i<=r;i++) if (check(i,r)) ret++;
return ret;
}
int main()
{
scanf("%d%d",&p,&k); s="#";
for (int i=;i<=p;i++) cin>>th,s+=th;
scanf("%d",&n);
for (int i=;i<=n;i++) cin>>mp[i];
m=s.length()-;
for (int i=;i<=m;i++)
for (int j=i;j<=m;j++)
val[i][j]=GetVal(i,j);
for (int i=;i<=m;i++)
for (int j=;j<=i;j++) {
# define k kk
for (int k=j-;k<=i-;k++)
f[i][j]=max(f[i][j],f[k][j-]+val[k+][i]);
#undef k
} printf("%d\n",f[m][k]);
return ;
}
P1026 统计单词个数
bzoj1999【数据加强版】
给定一棵n个点的带边权无根树，在其直径上求出一段长度不超过s的路径F，使得离路径距离最远的点到路径的距离最短。
求出这个离路径距离最远的点到路径的距离最短的值。
对于100%的数据$1 \leq n \leq 10^5 ，0 \leq w_i \leq 10^3 $
可以证明，路径F存在于任意一条直径上都可以得到答案。
考虑找出一条树的直径，拉成一条链，就是m个点m-1条边的链
二分一个答案MID
然后对于链上每一个点做一个最长链，记为$w_i$然后从链的两端往里跳，如果可以往里跳尽量往里跳（需要使用MID和$w_i$参数）
得到最终的左右区间[Left,Right]显然若区间为空那么一定可以，
若区间不为空，那么扫描[Left,Right]判断其$w_i$是不是超过了$MID$，其(Right-Left)条边权和是不是超过了限制$s$
然后转化为判定类问题。
复杂度$O(max\{N log_2T,n\}) $ 其中T表示最长链长度,N表示最长链节点数，n表示树节点个数。
可以过BZOJ加强版数据
# include <bits/stdc++.h>
using namespace std;
const int N=;
int dist[N],d[N],head[N],pre[N],w[N],f[N];
int n,m,s,tot,ans;
bool vis[N];
struct rec{
int pre,to,w;
}a[N<<];
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
void adde(int u,int v,int w)
{
a[++tot].pre=head[u];
a[tot].to=v;
a[tot].w=w;
head[u]=tot;
}
void dfs1(int u,int fath,int L)
{
dist[u]=L;
for (int i=head[u];i;i=a[i].pre){
int v=a[i].to;
if (v==fath) continue;
pre[v]=u;
dfs1(v,u,L+a[i].w);
}
}
void dfs2(int u,int fath,int L)
{
ans=max(ans,L); vis[u]=true;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to;
if (vis[v]) continue;
dfs2(v,u,L+a[i].w);
}
}
bool check(int MID)
{
# define lift Lift
# define Right Right
f[]=;
int left=d[],right=;
for (int i=;i<=d[];i++) {
f[i]=max(f[i-]+dist[i],w[i]);
if (f[i]>MID) {left=i; break;}
}
f[d[]+]=;
for (int i=d[];i>=;i--) {
f[i]=max(f[i+]+dist[i-],w[i]);
if (f[i]>MID) { right=i; break;}
}
if (left>right) return true;
int Sum=;
for (int i=left;i<=right;i++) {
if (w[i]>MID) return false;
if (i!=right) Sum+=dist[i];
}
if (Sum<=s) return true;
else return false;
#undef left
#undef right
}
void GetZhiJin()
{
dfs1(,,);
int p1=;
for (int i=;i<=n;i++) if (dist[i]>dist[p1]) p1=i;
dfs1(p1,,);
int p2=;
for (int i=;i<=n;i++) if (dist[i]>dist[p2]) p2=i;
swap(p1,p2);
while (p1!=p2) {
d[++d[]]=p1;
for (int i=head[p1];i;i=a[i].pre){
int v=a[i].to;
if (v==pre[p1]) dist[d[]]=a[i].w;
}
p1=pre[p1];
}
d[++d[]]=p2;
dist[d[]]=;
}
int main()
{
n=read();s=read();
for (int i=;i<=n;i++) {
int u=read(),v=read(),w=read();
adde(u,v,w),adde(v,u,w);
}
GetZhiJin();
int L=,R=;
for (int i=;i<=d[];i++) vis[d[i]]=true,R+=dist[i];
for (int i=;i<=d[];i++) {
ans=;
dfs2(d[i],,);
w[i]=ans;
}
while (L<=R) {
int mid=(L+R)>>;
if (check(mid)) ans=mid,R=mid-;
else L=mid+;
}
cout<<ans<<'\n';
return ;
}
BZOJ1999(Luogu P1099) 树网的核
求一棵n个节点的树，所有边权为$1$，距离为$2$的点对权值乘积最大值、权值乘积和，
其中权值乘积和需要对$10007$取模
对于100%的数据$n\leq 2\times 10^5 , 1 \leq w_i \leq 10^3$
枚举每个点考虑这个点连接到的若干个点，设这个集合为S，那么S重的点互相两两配对都是符合条件的点对。
然后考虑最大值显然是S中两个最大的点权相乘，求和显然是每一个点和前面的点贡献和的2倍，维护即可
复杂度O(kn)，其中k表示节点的直接儿子数的平均值，可以看做常数
# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=+;
const int mo=;
int val[N],tot,head[N];
struct rec{int pre,to;}a[N<<];
void adde(int u,int v)
{
a[++tot].pre=head[u];
a[tot].to=v;
head[u]=tot;
}
signed main()
{
int n; scanf("%lld",&n);
int u,v;
for (int i=;i<=n;i++) {
scanf("%lld%lld",&u,&v);
adde(u,v); adde(v,u);
}
for (int i=;i<=n;i++) scanf("%lld",&val[i]);
int ans1=,ans2=;
for (int i=;i<=n;i++) {
int u=i;
int ret=;
int last_sum=;
int max1=,pos1;
for (int i=head[u];i;i=a[i].pre){
int v=a[i].to;
ret+=last_sum*val[v]%mo; ret%=mo;
last_sum+=val[v]%mo; last_sum%=mo;
if (max1<val[v]) max1=val[v],pos1=v;
}
int max2=;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to;
if (max2<val[v]&&v!=pos1) max2=val[v];
}
ans1=max(ans1,max1*max2);
ans2+=(ret<<)%mo; ans2%=mo;
}
cout<<ans1<<' '<<ans2<<'\n';
return ;
}
P1351 联合权值
给出$n \times m$的网格图每个点(i,j)表示该点的高度，然后考虑水只能从高处流向低处。
在第一行设k个取水站然后要求最后一行所有城市都可以流经水，若可能最小化k，若不可能求有多少个城市无法流经水
对于100%的数据$n,m \leq 500$
考虑一个$O(n^3)$算法求出第一行每一个点可以覆盖到最后一行多少点，我们可以证明覆盖的一定是一个区间：
若覆盖不是一个区间那么可能存在2条路径相交，而水可以选取任意一条路径流下，那么这两个区间不是独立的，
必然有交集而形成一个独立的1个区间。
然后在给出的若干个区间做线段覆盖若不能覆盖[1,n]计算30%的答案，若能覆盖那么计算剩余70%的答案
贪心做法如下：左端点排序，然后取头线段看后面头在头线段区间之间那么尽可能往右拓展。排序即可。
常数优化，当且仅当第一行高度比两边都高才进行搜索，显然更优（因为ta隔壁到的ta一定可以到）。
// luogu-judger-enable-o2
# include <bits/stdc++.h>
using namespace std;
const int N=;
const int dx[]={-,,,};
const int dy[]={,,,-};
int mp[N][N],a[N][N],get[N];
int n,m,num;
bool use[N][N];
struct node{int x,y;};
struct rec{int l,r;}w[N];
queue<node>q;
bool cmp(rec a, rec b){return a.l<b.l;}
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
void bfs(int sx,int sy)
{
memset(use,false,sizeof(use));
q.push((node){sx,sy});
use[sx][sy]=true;
while (!q.empty()) {
node u=q.front(); q.pop();
for (int i=;i<;i++) {
node v; v.x=u.x+dx[i];v.y=u.y+dy[i];
if (v.x<||v.x>n||v.y<||v.y>m||use[v.x][v.y]) continue;
if (a[u.x][u.y]<=a[v.x][v.y]) continue;
use[v.x][v.y]=true;
q.push(v);
}
}
for (int i=;i<=m;i++)
if (use[n][i]) get[i]=true;
int L=,R=;
for (int i=;i<=m;i++)
if (use[n][i]) { L=i; break;}
for (int i=m;i>=;i--)
if (use[n][i]) { R=i; break;}
if (L==&&R==) return;
w[++num]=(rec){L,R};
}
int main()
{
n=read();m=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
a[i][j]=read();
for (int i=;i<=m;i++) bfs(,i);
int ret=;
for (int i=;i<=m;i++)
if (get[i]) ret++;
if (ret<m) {
printf("0\n%d\n",m-ret);
return ;
}
sort(w+,w++num,cmp);
int i=,j=,ans=;
while (j<=m) {
int t=;
while (w[i].l<=j) {
t=max(t,w[i].r);
i++;
}
j=t+;ans++;
}
printf("1\n%d\n",ans);
return ;
}
P1514 引水入城
有n门课程，分在2n个教室上课c[i]和d[i]，然后对教室之间有无向图{v,e}联通，每次从一教室走到另一教室走最短路。
第i门课程默认在c[i]上课，但是可以最多选择m门课程换到d[i]教室上课，有k[i]的期望换教室成功，确定申报若干个教室编号
使得完成n门课程期望行走路程最短，输出期望最短总路程长度。
对于100%的数据，$v \leq 300,n,m \leq 2000,$图可能会有重边和自环
考虑若选择当前教室申报和不选择当前教室申报期望是不同的，或者说一个有期望，一个没有期望。
所以要设计一维状态0/1表示当前教室选不选择申报。
所以显然的设计$f[i][j][0/1]$表示前 i 节课使用 j 次申报其中第 i 节课 不申报/申报 换教室最小期望总路程长度
考虑$f[i][j][0]$的转移，显然是从$i-1$转移而来，
第1种 第$i-1$节课不申请，所以对于$i-1$到$i$是唯一的一种可能期望路径 从$c[i-1]$走到$c[i]$，得$f[i-1][j][0]+dist(c[i-1],c[i])$
第2种 第$i-1$节课申请 ， 所以对于$i-1$到$i$有2种可能的期望路径，从$c[i-1]$到$c[i]$($i-1$换课不成功)，从$d[i-1]$到$c[i]$($i-1$换课成功)，
得$f[i-1][j][1]+k[i-1]\times dist(d[i-1],c[i]) + (1-k[i-1]) \times dist(c[i-1],c[i])$
综上所述$f[i][j][0]=max\{ f[i-1][j][1]+k[i-1]\times dist(d[i-1],c[i]) + (1-k[i-1]) \times dist(c[i-1],c[i]) , f[i-1][j][0]+dist(c[i-1],c[i]) \}$
考虑$f[i][j][1]$的转移，显然是从$i-1$转移而来，
第1种 第$i-1$节课不申请，所以对于$i-1$到$i$有2种可能的期望路径，从$c[i-1]$到$c[i]$($i$换课不成功)，从$c[i-1]$到$d[i]$($i$换课成功)，
得$f[i-1][j-1][0]+k[i]\times dist(c[i-1],d[i])+(1-k[i])\times dist(c[i-1],d[i]) $
第2种 第$i-1$节课申请 ， 所以对于$i-1$到$i$有$2 \times 2$种可能的期望路径，
从$c[i-1]$到$c[i]$($i-1,i$换课不成功)，得 $(1-k[i-1]) \times (1-k[i]) \times dist(c[i-1],c[i])$
从$c[i-1]$到$d[i]$($i-1$换课不成功，$i$换课成功)，得$((1-k[i-1])\times k[i] \times dist(c[i-1],d[i]) $
从$d[i-1]$到$c[i]$($i-1$换课成功，$i$换课不成功)，得$k[i-1]\times (1-k[i]) \times dist(d[i-1],c[i])$
从$d[i-1]$到$d[i]$($i-1,i$换课成功)，得$k[i-1] \times k[i] \times dist(d[i-1],d[i]) $
综上所述 $f[i][j][1]=max \{f[i-1][j-1][1]+(1-k[i-1]) \times (1-k[i]) \times dist(c[i-1],c[i]) +$
$ ((1-k[i-1])\times k[i] \times dist(c[i-1],d[i]) + $
$k[i-1]\times (1-k[i]) \times dist(d[i-1],c[i]) + $
$ k[i-1] \times k[i] \times dist(d[i-1],d[i]) $
$, f[i-1][j-1][0]+k[i]\times dist(c[i-1],d[i])+(1-k[i])\times dist(c[i-1],d[i]) \}$
然后考虑j=0的边界转移,若 k=0 只能从i-1不换课，转移，而k=1根本不能
边界f[1][0][0]=0,f[1][1][1]=0,f[][][]=INF
答案是$Min\{ f[n][i][0],f[n][i][1] \} (0 \leq i \leq m)$
# include <bits/stdc++.h>
# define fp(i,s,t) for (int i=s;i<=t;i++)
# define INF (<<)
using namespace std;
const int N=2e3+;
int c[N],d[N];
double mp[N][N];
int n,m,v,e;
double f[N][N][],k[N];
double Min(double a,double b)
{
if (a<b) return a; else return b;
}
void floyd()
{
fp(k,,v) fp(i,,v) fp(j,,v)
if (k!=i&&i!=j&&j!=k)
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
double D(int x,int y){return mp[x][y];}
signed main()
{
scanf("%d%d%d%d",&n,&m,&v,&e);
fp(i,,n) scanf("%d",&c[i]);
fp(i,,n) scanf("%d",&d[i]);
fp(i,,n) scanf("%lf",&k[i]);
fp(i,,v) fp(j,,v) mp[i][j]=(i==j||i==||j==?:INF);
fp(i,,e) {
int u,v; double w;
scanf("%d%d%lf",&u,&v,&w);
mp[u][v]=mp[v][u]=Min(mp[u][v],w);
}
floyd();
fp(i,,n) fp(j,,m) f[i][j][]=f[i][j][]=INF;
f[][][]=0.0; f[][][]=0.0;
fp(i,,n) {
f[i][][]=f[i-][][]+D(c[i-],c[i]);
fp(j,,min(i,m)) {
f[i][j][]=Min(f[i-][j][]+D(c[i-],c[i]),f[i-][j][]+k[i-]*D(d[i-],c[i])+(-k[i-])*D(c[i-],c[i]));//i没尝试去换
f[i][j][]=Min(f[i-][j-][]+k[i]*D(c[i-],d[i])+(-k[i])*D(c[i-],c[i]),
f[i-][j-][]+k[i-]*k[i]*D(d[i-],d[i])+k[i-]*(-k[i])*D(d[i-],c[i])+(-k[i-])*k[i]*D(c[i-],d[i])+(-k[i-])*(-k[i])*D(c[i-],c[i]));
}
}
double ans=INF;
fp(i,,m) ans=Min(ans,Min(f[n][i][],f[n][i][]));
printf("%.2lf\n",ans);
return ;
}
P1850 换教室
有n列m行的网格左下角是(0,0),小鸟每一单位时间横坐标右移1单位，纵坐标在时刻i（出发时为0时刻）有两种情况
- 1. 自由下落，纵坐标下降Y[i]；
- 2. 花费k$(k >0)$的代价上升$k \times$X[i]。
注意一点：当点k次后小鸟高度超过m那么会停留在上边缘。
有k个管道，给出每个管道位置$p_i$，下表面距离x轴高度$L_i$，上表面距离x轴高度$H_i$
管道覆盖处（下表面高度以下，上表面高度以上）、地面（即x轴）不能触碰。
此时会有两种可能，
- 若从0列任意位置出发不可能到达n列，输出0\n，然后输出最多通过管道数
- 若从0列任意位置出发能够到达n列，输出1\n，然后输出最小代价(点击次数)
对于70%的数据，$ 5 \leq n\leq 10^3 ,5 \leq m\leq 10^2$
对于85%的数据，$X[i],Y[i]$较为随机，且开启O2常数优化
对于100%的数据，$5 \leq n \leq 10^4$, $5 \leq m \leq 10^3$，$0 \leq k < n$, $0 < X < m$, $0 < Y < m$, $0 < P < n$, $0 \leq L < H \leq m$, $L + 1 < H$
01背包和完全背包综合体。
我们会有一个简单的想法，暴力转移，对于以左下角作为(0,0)点的坐标系来说从i-1列到i列可以有两种转移方式。
记f[i][j]表示小鸟到(i,j)位置(即i列j高度)最小代价。
对于一般情况($j\neq m$)，显然是从$f[i-1][j+Y[i-1]]$和$f[i-1][j-k\times X[i-1] ]+k$转移而来。
对于特殊情况($j=m$)，只能从i-1列m及以下行某一处跳至少1次到达，跳1次跳到顶部$f[i-1][j-k]+1(k \in [j-X[i-1],m])$,跳2次以上跳到顶部$f[i][j-k]+1(k \in [j-X[i-1],m])$，即这次跳到(i,j-X[i-1])最小代价了如果再跳1次一定可以到达顶部。
复杂度O(knm)，显然k取决于数据的随机程度，若给出X[i-1]较小那么程序复杂度会较大。
对于本题即使数据已经比较随机，给出X[]和Y[]以上算法在开启O2优化的情况下能够得70-85分
开启O2优化85分代码：
// luogu-judger-enable-o2
# include <bits/stdc++.h>
# define inf (0x3f3f3f3f)
using namespace std;
const int N=1e4+,M=1e3+;
int f[N][M],down[N],up[N],x[N],y[N],pou[N];
int n,m,p;
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
int main()
{
n=read();m=read();p=read();
for (int i=;i<n;i++)
x[i]=read(),y[i]=read();
for (int i=;i<=n;i++) down[i]=,up[i]=m+;
for (int i=;i<=p;i++) {
int pos=read();
down[pos]=read(); up[pos]=read();
pou[pos]=;
}
memset(f,0x3f,sizeof(f));
for (int i=;i<=m;i++) f[][i]=;
int rp;
for (int i=;i<=n;i++) {
for (int j=;j<=m;j++) {
if (j==m) {
for (int k=m-x[i-];k<=m;k++) {
f[i][m]=min(f[i][m],f[i-][k]+);
f[i][m]=min(f[i][m],f[i][k]+);
}
}
int k=;
while (true) {
if (j-k*x[i-]<=||f[i][j]<=k) break;
f[i][j]=min(f[i][j],f[i-][j-k*x[i-]]+k);
k++;
}
}
for (int j=;j<=m;j++)
if (j+y[i-]<=m) f[i][j]=min(f[i][j],f[i-][j+y[i-]]);
for (int j=;j<=down[i];j++) f[i][j]=inf;
for (int j=up[i];j<=m;j++) f[i][j]=inf;
for (int j=;j<=m;j++) if (f[i][j]!=inf) rp=i;
}
int Ans=inf;
for (int i=;i<=m;i++) Ans=min(Ans,f[n][i]);
if (Ans!=inf) {
printf("1\n%d\n",Ans);
return ;
}
Ans=;
for (int i=;i<=rp;i++)
if (pou[i]==) Ans++;
printf("0\n%d\n",Ans);
return ;
}
P1941 飞扬的小鸟-85pts
考虑优化常数k，主要是做背包的时候枚举了个数k，可以考虑使用上述特判处的思想，从i这一列已经转移成功的那一行转移过来代替枚举的k，充分利用求得的东西，即f[i][j]从f[i][j-X[i-1]]+1转移过来，即跳到(i,j-X[i-1])已经最小化步数，再多点1次就跳到(i,j)了。
复杂度O(nm)
注意上述dp需要注意边界问题，不要出现负数下标，即使排除不可能决策的转移方案。
然后最后赋值水管位置为inf，两个背包分开来转移。
不开启O2优化100分代码：
# include <bits/stdc++.h>
# define inf (0x3f3f3f3f)
using namespace std;
const int N=1e4+,M=1e3+;
int f[N][M],down[N],up[N],x[N],y[N],pou[N];
int n,m,p;
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
int main()
{
n=read();m=read();p=read();
for (int i=;i<n;i++)
x[i]=read(),y[i]=read();
for (int i=;i<=n;i++) down[i]=,up[i]=m+;
for (int i=;i<=p;i++) {
int pos=read();
down[pos]=read(); up[pos]=read();
pou[pos]=;
}
memset(f,0x3f,sizeof(f));
for (int i=;i<=m;i++) f[][i]=;
int rp;
for (int i=;i<=n;i++) {
for (int j=;j<=m;j++) {
if (j==m) {
for (int k=m-x[i-];k<=m;k++) {
f[i][m]=min(f[i][m],f[i-][k]+);
f[i][m]=min(f[i][m],f[i][k]+);
}
}
if (j-x[i-]>) f[i][j]=min(f[i][j],f[i-][j-x[i-]]+);
if (j-x[i-]>) f[i][j]=min(f[i][j],f[i][j-x[i-]]+);
}
for (int j=;j<=m;j++)
if (j+y[i-]<=m) f[i][j]=min(f[i][j],f[i-][j+y[i-]]);
for (int j=;j<=down[i];j++) f[i][j]=inf;
for (int j=up[i];j<=m;j++) f[i][j]=inf;
for (int j=;j<=m;j++) if (f[i][j]!=inf) rp=i;
}
int Ans=inf;
for (int i=;i<=m;i++) Ans=min(Ans,f[n][i]);
if (Ans<inf) {
printf("1\n%d\n",Ans);
return ;
}
Ans=;
for (int i=;i<=rp;i++)
if (pou[i]==) Ans++;
printf("0\n%d\n",Ans);
return ;
}
P1941 飞扬的小鸟-100pts
最新文章
- be supposed to
- 如何学习Python
- SQL语句 & 查询表结构
- VS下遇到未能加载文件或程序集 错误
- maven jetty plugin
- 获取ajax对象
- latex 批量注释
- xml的生成和发送
- 如何在RHEL7上搭建Samba服务实现Windows与Linux之间的文件共享
- 2D图形如何运动模拟出3D效果
- Java开发规范总结
- WebSocket对象的“readyState”属性记录连接过程中的状态值
- 将表单数据转换为json代码分享
- Topcoder的使用方法
- 浅谈原生JavaScript实现remove()和recover()
- linux基础02-bash特性
- Unknown type name 'NSString' 解决方案
- 170822、解决PLSQL记录被另一个用户锁住的问题
- Netty 系列（三）Netty 入门
- 有关linqtosql和EF的区别