首页 > 代码库 > POJ 1201 差分方程分析

POJ 1201 差分方程分析

2024-07-14 15:53:46   223人阅读

POJ 1201

给你N个闭区间。每个区间分别为[ai,bi]，你必须在这个区间上至少取ci个不同的整数。

现要求所有区间满足各自的条件。

问最少需要选多少个点。

例如[3,7](3)  [8,10](3)  [6,8](1)  [1,3](1)  [10,11](1)

我们最少需要选6个点:

3 4 6 8 9 10

 

在这里我们可以看成是dp[7]-dp[2]>=3 dp[10]-dp[8]>=3 ....

这就可以理解为2->7的距离可以定为3,8->10的距离也定为3

我们再看看Si的定义，也不难写出0<=Si - Si-1<=1的限制条件，虽然看上去是没有什么意义的条件，但是如果你也把它构造出一系列的边的话，这样从起点到终点的最短路也就顺理成章的出现了。

我们将上面的限制条件写为同意的形式：

Sbi - Sai >= ci

Si - Si-1 >= 0

Si-1 - Si >= -1

这样子我们相当于在一个构建好的有向图中找一个最长路径，这跟之前的最短路径正好相反，所以需要引起注意

那么dp在初始化时需尽可能小，才能不断更新出最大值

 1 memset(dp,-1,sizeof(dp)); 
for(int i=first[u];i!=-1;i=area[i].next){            if(dp[area[i].y]<dp[u]+area[i].d){                dp[area[i].y]=dp[u]+area[i].d;                if(!visit[area[i].y])                    visit[area[i].y]=1,q.push(area[i].y);            }


所以这里要引起注意，要在小于的情况下继续执行程序，不断更新出最大值。

 

对于一个差分问题来说是可能存在无解的情况的，那说明形成的是负圈，但这道题目明显表示有解，所以无需进行负圈的判断。

总代码如下：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <cmath> 6 using namespace std; 7 #define N 50005 8 #define M 200000 9 10 int visit[N],dp[N],first[N],k,n,m,maxn,minn;11 12 struct Area{13     int y,next,d;14 }area[M];15 16 void init()17 {18     k=0,maxn=0,minn=N;19     memset(first,-1,sizeof(first));20 }21 22 void add(int a,int b,int c){23     area[k].y=b,area[k].d=c,area[k].next=first[a];24     first[a]=k;25     k++;26 }27 28 void spfa()29 {30     memset(visit,0,sizeof(visit));31     queue<int> q;32     memset(dp,-1,sizeof(dp));33     dp[minn]=0,visit[minn]=1,q.push(minn);34     while(!q.empty()){35         int u=q.front();36         q.pop();37         visit[u]=0;38         for(int i=first[u];i!=-1;i=area[i].next){39             if(dp[area[i].y]<dp[u]+area[i].d){40                 dp[area[i].y]=dp[u]+area[i].d;41                 if(!visit[area[i].y])42                     visit[area[i].y]=1,q.push(area[i].y);43             }44         }45     }46 }47 48 int main()49 {50     int a,b,c;51     while(scanf("%d",&n)!=EOF){52         init();53         for(int i=0;i<n;i++)54         {55             scanf("%d%d%d",&a,&b,&c);56             //add(b,a-1,-c);57             add(a,b+1,c);58             maxn=max(maxn,b+1);59             minn=min(minn,a);60         }61         for(int i=minn;i<maxn;i++){62             add(i,i+1,0);63             add(i+1,i,-1);64         }65         spfa();66 67         printf("%d\n",dp[maxn]);68     }69     return 0;70 }

 

 


联系
我们