首先，这是一道背包，嗯，背包就不难，所以不用题解，再见！！
好了，言归正传，这道题之所以是绿题，就是因为它太细了！！
首先是一个 m*n 的一个平面，求到终点所需点击屏幕的最小值。
那我们不妨用f（i,j）来表示到坐标(i,j)所需点击屏幕的最小值。
然后怎么往后推呢？//用laffey的话来说“lao zi bu hui”
对于每一个横坐标i来说，它下一个坐标一定是i+1(废话，要不还能是i呢)
然后对于每一个i来说，它有两种状态，即点击屏幕&&不点击屏幕
所以就有了这个递推式
f[i][j]=min(f[i][j],min(f[i-1][j-x],f[i][j-x]))//没错，它下一个坐标真的可以是i
f[i][j]=min(f[i][j],f[i-1][j+y])
其实点击屏幕就是一个完全背包，不点击就是一个01背包
递推式已经有了，还A不了吗？后面你还要看？
好吧，然后是处理管道是吧。
这玩意非常好处理，你不是有管道的坐标吗，在递推到管道的时候把它给定义成0x3f3f3f3f就OK了
什么，你看到这里还A不了？是不是应该反思一下。
后面是什么问题，我猜猜啊！
是不是不会找能过几个管道啊，行了代码给你，剩下的自己写吧。
int mn=mk,cnt=k;
for(int i=n;i>=1;i--)
{
for(int j=l[i]+1;j<g[i];j++)if(f[i][j]<mk)mn=min(mn,f[i][j]);//l[i]表示每一个的最低点，平时是0，管道处是管道的下边高度。g[i]是上边的
if(mn!=mk)break;
if(g[i]<=m)cnt--;
}
if(cnt==k)cout<<1<<endl<<mn;
else cout<<0<<endl<<cnt;
什么，你还没A！！！
又是什么问题？
没处理到 j==m 吗？这你不能，至少不应该吧。
行了代码拿去。
for(int j=1;j<=m;j++)
{
if(j>h[i].x)
f[i][j]=min(f[i][j],min(f[i-1][j-h[i].x]+1,f[i][j-h[i].x]+1));
if(j==m)
{
for(int t=m-h[i].x;t<=m;t++)
f[i][j]=min(f[i][j],min(f[i][t]+1,f[i-1][t]+1));
}
}
你不会还没A吧，又是什么问题啊？
哦，你不会先处理的下降吧！
你先下降的话，在上升是不是有点问题啊；
没错，就是这玩意（f(i,j)=f(i,j-x)）
好了，这题也没啥好说的了，代码给你，剩下还有什么问题自己找吧。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,k,m;
struct yzy{
int x,y;
}h[N];
const int mk=0x3f3f3f3f;
int l[N],g[N];
int f[10010][1010];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>h[i].x>>h[i].y;
for(int i=1;i<=n;i++)
{
l[i]=0;
g[i]=m+1;
}
for(int i=1;i<=k;i++)
{
int p,a,s;
cin>>p>>a>>s;
l[p]=a;g[p]=s;
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;i++)
f[0][i]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j>h[i].x)
f[i][j]=min(f[i][j],min(f[i-1][j-h[i].x]+1,f[i][j-h[i].x]+1));
if(j==m)
{
for(int t=m-h[i].x;t<=m;t++)
f[i][j]=min(f[i][j],min(f[i][t]+1,f[i-1][t]+1));
}
}
for(int j=g[i]-1;j>=l[i]+1;j--)
{
if(m-j>=h[i].y)
{
f[i][j]=min(f[i][j],f[i-1][j+h[i].y]);
}
}
for(int j=1;j<=l[i];j++)
f[i][j]=mk;
for(int j=m;j>=g[i];j--)
f[i][j]=mk;
}
int mn=mk,cnt=k;
for(int i=n;i>=1;i--)
{
for(int j=l[i]+1;j<g[i];j++)if(f[i][j]<mk)mn=min(mn,f[i][j]);
if(mn!=mk)break;
if(g[i]<=m)cnt--;
}
if(cnt==k)cout<<1<<endl<<mn;
else cout<<0<<endl<<cnt;
return 0;
}
共 2 条回复
还有谁题？QAQ
所以为什么要接我题