基本相同的代码,为啥一个70一个100?
查看原帖
基本相同的代码,为啥一个70一个100?
1308728
xsmfollower楼主2024/5/17 21:55

70:

#include<cstdio>
#include<cstring>
using namespace std;
const int L=1e6+10,INF=0x3f3f3f3f; int dp[L],d[L],q[L]; bool vis[L];
int main() {
  int n,l,a,b,h=1,t=1; scanf("%d %d %d %d",&n,&l,&a,&b);
  for(int i=1,s,e;i<=n;i++) scanf("%d %d",&s,&e),d[s+1]++,d[e]--;
  for(int i=1;i<=l;i++) vis[i]=vis[i-1]+d[i];
  memset(dp,0x3f,sizeof(dp)),dp[0]=0;
  for(int i=2*a;i<=l;i+=2) {
    while(h<t&&i-q[h]>2*b) h++;
    while(h<t&&dp[i-2*a]<=dp[q[t-1]]) t--;
	q[t++]=i-2*a;
    if(!vis[i]) dp[i]=dp[q[h]]+1;
  }
  if(dp[l]>=INF) printf("-1");
  else printf("%d",dp[l]);
  return 0;
}

100:

#include<cstdio>
#include<cstring>
using namespace std;
const int L=1e6+10,INF=0x3f3f3f3f; int dp[L],d[L],q[L];
int main() {
  int n,l,a,b,h=1,t=1; scanf("%d %d %d %d",&n,&l,&a,&b);
  for(int i=1,s,e;i<=n;i++) scanf("%d %d",&s,&e),d[s+1]++,d[e]--;
  for(int i=1;i<=l;i++) d[i]+=d[i-1];
  memset(dp,0x3f,sizeof(dp)),dp[0]=0;
  for(int i=2*a;i<=l;i+=2) {
    while(h<t&&i-q[h]>2*b) h++;
    while(h<t&&dp[i-2*a]<=dp[q[t-1]]) t--;
	q[t++]=i-2*a;
    if(!d[i]) dp[i]=dp[q[h]]+1;
  }
  if(dp[l]>=INF) printf("-1");
  else printf("%d",dp[l]);
  return 0;
}
2024/5/17 21:55
加载中...