我也75……
by ZigZagKmp @ 2018-08-20 22:33:23
你是不是WA #4 #7 #8 #10 #11?
by ZigZagKmp @ 2018-08-20 22:34:16
```cpp
#include <bits/stdc++.h>
using namespace std;
#define maxn 10000+5
#define maxm 1000+5
#define inf 0x3f3f3f3f
#define LL long long int
#define mod 10007
#define local
#define max(a,b)((a)>(b)?(a):(b))
#define min(a,b)((a)<(b)?(a):(b))
#define abs(a)((a)>0?(a):(-a))
int n,m,k;
int able[maxn][maxm],dp[maxn][maxm],wu[maxn],wd[maxn];
int as[maxn];
inline void in(){
int bb[maxn];
memset(bb,0,sizeof(bb));
read(n);read(m);read(k);//快速读入代码没贴
for(register int i=1;i<=n;i++){
read(wu[i]);read(wd[i]);
}
int x,d,u;
for(register int i=1;i<=k;i++){
read(x);read(d);read(u);
bb[x]++;
for(register int j=u;j<=m;j++)able[x][j]=1;
for(register int j=d;j;j--)able[x][j]=1;
}
for(register int i=0;i<=n;i++)able[i][0]=1;
for(register int i=1;i<=n;i++){
as[i]=as[i-1]+bb[i];//as数组保存当前位置已经跨过的管道数量(包括当前的)。
}
}
int ok,ans;
inline void pre(){
ok=1;ans=inf;
memset(dp,0x3f,sizeof(dp));
for(register int i=1;i<=m;i++)dp[0][i]=0;
}
inline void out(){
printf("%d\n",ok);
if(ok){
for(register int i=1;i<=m;i++)ans=min(ans,dp[n][i]);
}
printf("%d\n",ans);
}
inline void wo(){
bool flag;
for(register int i=1;i<=n;i++){
flag=0;
for(register int j=1;j<=m;j++){
if(j-wu[i]>0&&!able[i][j]&&dp[i-1][j-wu[i]]!=inf){
dp[i][j]=min(dp[i][j],dp[i-1][j-wu[i]]+1);
}
}//上升1次
for(register int j=1;j<=m;j++){
if(j-wu[i]>0&&!able[i][j]&&dp[i][j-wu[i]]!=inf){
dp[i][j]=min(dp[i][j],dp[i][j-wu[i]]+1);
}
}//上升多次
for(register int j=m-wu[i];j<=m;j++){
if(able[i][m])continue;
if(dp[i-1][j]!=inf)dp[i][m]=min(dp[i][m],dp[i-1][j]+1);
if(dp[i][j]!=inf)dp[i][m]=min(dp[i][m],dp[i][j]+1);
}//到顶的特判
for(register int j=m;j;j--){
if(j+wd[i]<=m&&!able[i][j]&&dp[i-1][j+wd[i]]!=inf){
dp[i][j]=min(dp[i][j],dp[i-1][j+wd[i]]);
}
}//下降
for(register int j=1;j<=m;j++)if(dp[i][j]!=inf){flag=1;break;}//无解判断
if(!flag){
ok=0;ans=as[i-1];
return;
}
}
}
int main(){
in();
pre();
wo();
out();
return 0;
}
```
by ZigZagKmp @ 2018-08-20 22:38:42
@[周子凯](/space/show?uid=35871) 我也75,但我WA #5 #7 #10 #11 #13,都是比正确答案多一点
by _King__ @ 2018-08-22 11:19:52