数组开大点,
by Hammer_cwz_77 @ 2017-11-03 13:19:49
换个问题:怎么把上升那段改为完全背包?TLE 5个点(刷表法)
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10001;
const int inf=0x3f3f3f3f;
int n,m,k,x[N],y[N];
int pp[N],h[N],l[N];
int dp[2][1001],sum;
int main() {
freopen("bird.in","r",stdin);
//freopen("bird.out","w",stdout);
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,p; i<=k; i++) {
scanf("%d%d%d",&p,&l[i],&h[i]);
pp[p]=i;
}
l[0]=0,h[0]=m+1;
memset(dp,0x3f,sizeof dp);
int now(0),next(1);
for(int i=1; i<=m; i++) {
dp[now][i]=0;
}
for(int i=0; i<n; i++) {
bool flag=0;
for(int j=l[pp[i]]+1; j<h[pp[i]]; j++) {
if(dp[now][j]==inf) continue;
flag=1;
for(int k=1;k<=100; k++) {
int t=j+x[i]*k;
if(t<=l[pp[i+1]]) continue;//触碰下面一节
if(t>=h[pp[i+1]]||t>=m) {//触碰上面一节或抵框
if(h[pp[i+1]]==m+1) {//抵框
dp[next][m]=min(dp[next][m],dp[now][j]+k);
}
break;
}
dp[next][t]=min(dp[next][t],dp[now][j]+k);
}
int t=j-y[i];
if(t>l[pp[i+1]]&&t<h[pp[i+1]]) {
dp[next][t]=min(dp[next][t],dp[now][j]);
}
}
if(!flag) {
printf("0\n%d\n",sum);
return 0;
}
sum+=(pp[i]!=0);
for(int j=0; j<=m+1; j++) {
dp[now][j]=inf;
}
next^=now^=next^=now;
}
int ans=*min_element(dp[now]+1,dp[now]+m+1);
printf("1\n%d\n",ans);
}
```
by 早右昕 @ 2017-11-03 13:20:48
你有没有wa的点
by 李寻欢 @ 2018-02-09 20:57:28