这题之前做过…先听后做的 所以直接打了优化的dp、 然而不是自己想的方法还是理解的不好 一直75分 wa到挺 今天考试看到暴力dp70分 很自信加上点 continue break啥的就80+了 比优化的dp得分多 机智的我哈哈哈….. 然而手残了..枚举k次蹦跶结果转移的时候我特么都是+1不是+k 悲伤的我眼泪掉下来….. 然后改过来就80了 又不好办了.. 下面是80分代码 #include<iostream> #include<cstdio> #include<cstring> #define maxn 10010 using namespace std; int n,m,K,f[maxn][maxn/10],ans=0x7fffffff,s; int Xi[maxn],Sh[maxn],X[maxn],Y[maxn],falg[maxn];//X 为上 Y为下 int main() { scanf("%d%d%d",&n,&m,&K); for(int i=0;i<n;i++) scanf("%d%d",&X[i],&Y[i]); for(int i=1;i<=n;i++) Xi[i]=0,Sh[i]=m+1; int x,y,z; for(int i=1;i<=K;i++) { scanf("%d%d%d",&x,&y,&z); Xi[x]=y;Sh[x]=z;falg[x]=1; } memset(f,127/3,sizeof(f)); for(int i=1;i<=m;i++)f[0][i]=0; for(int i=0;i<n;i++) for(int j=1;j<=m;j++) { if(f[i][j]==f[0][0])continue; int ii,jj,li=m/X[i]+1; for(int k=1;k<=li;k++) { ii=i+1,jj=j+k*X[i];if(jj>m)jj=m; if(jj<=Xi[ii]||jj>=Sh[ii])continue; f[ii][jj]=min(f[ii][jj],f[i][j]+k); } ii=i+1;jj=j-Y[i]; if(jj<=Xi[ii]||jj>=Sh[ii])continue; f[ii][jj]=min(f[ii][jj],f[i][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(f[i][j]<f[0][0]&&falg[i]==1) { s++;break; } for(int i=1;i<=m;i++) ans=min(ans,f[n][i]); if(s==K)printf("1 %d ",ans); else printf("0 %d ",s); return 0; } 后来同桌终于在提交40+遍之后找到了错误 真是 隐蔽…. 果然不是自己想的方法不好差错误啊… 这里的优化是省掉了枚举蹦跶几次 那蹦跶好几次的怎么办呢 可以认为他是先蹦跶到i,j 的下面I,j-h的地方然后在一次到I j 图自己脑补一下. 注意先处理上升在处理下落 要不可能上升时用到的状态的刚才下落来的. 下面是wa到挺得75分 #include<iostream> #include<cstdio> #include<cstring> #define inf 10000 #define maxn 10010 using namespace std; int n,m,k,up[maxn],down[maxn],ans=inf,now; int lu[maxn],ld[maxn],f[maxn][maxn/10],far; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { scanf("%d%d",&up[i],&down[i]); lu[i]=m+1;ld[i]=0; } int x,y,z; for(int i=1;i<=k;i++) { scanf("%d%d%d",&x,&y,&z); ld[x]=y;lu[x]=z; } memset(f,127/3,sizeof(f)); for(int i=0;i<=m;i++)f[0][i]=0; for(int i=1;i<=n;i++) { if(ld[i]!=0||lu[i]!=m+1)now++; for(int j=1;j<=m;j++) { int ji=j+up[i];if(ji>m)ji=m; if(ji<=ld[i]||ji>=lu[i])continue; f[i][ji]=min(f[i][ji],f[i-1][j]+1); f[i][ji]=min(f[i][ji],f[i][j]+1); if(i==n)ans=min(ans,f[i][ji]); if(f[i][ji]<inf)far=now; } for(int j=1;j<=m;j++) { int ji=j-down[i]; if(ji<=ld[i]||ji>=lu[i])continue; f[i][ji]=min(f[i][ji],f[i-1][j]); if(i==n)ans=min(ans,f[i][ji]); if(f[i][ji]<inf)far=now; } } for(int i=1;i<=m;i++) ans=min(ans,f[n][i]); if(far==k)printf("1 %d ",ans); else printf("0 %d ",far); return 0; } 错误出在那两个continue上… 可能出现那种省略掉k的转移正好来自柱子上 但是他是我们脑补出来的 他是合法的状态 所以不能continue掉 应该先更新完 再给柱子弄成inf #include<iostream> #include<cstdio> #include<cstring> #define maxn 10010 #define inf 707406378 using namespace std; int n,m,k,up[maxn],down[maxn],ans=0x7fffffff,now; int lu[maxn],ld[maxn],f[maxn][maxn/10],far,falg[maxn]; int min(int a,int b) { return a<b?a:b; } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++) { scanf("%d%d",&up[i],&down[i]); lu[i]=m+1;ld[i]=0; } ld[n]=0;lu[n]=m+1; int x,y,z; for(int i=1;i<=k;i++) { scanf("%d%d%d",&x,&y,&z); ld[x]=y;lu[x]=z;falg[x]=1; } memset(f,127/3,sizeof(f)); for(int i=0;i<=m;i++)f[0][i]=0; for(int i=0;i<n;i++) { for(int j=1;j<=m;j++) { int ji=j+up[i],ii=i+1;if(ji>m)ji=m; f[ii][ji]=min(f[ii][ji],f[i][j]+1); f[ii][ji]=min(f[ii][ji],f[ii][j]+1); } for(int j=1;j<=m;j++) if(j<=ld[i+1]||j>=lu[i+1])f[i+1][j]=inf; for(int j=1;j<=m;j++) { int ji=j-down[i],ii=i+1; if(ji<=ld[ii]||ji>=lu[ii])continue; f[ii][ji]=min(f[ii][ji],f[i][j]); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(f[i][j]<inf&&falg[i]==1) { far++;break; } for(int i=1;i<=m;i++) ans=min(ans,f[n][i]); if(far==k)printf("1 %d ",ans); else printf("0 %d ",far); return 0; }