GCJ EMEA Semifinal 2008 Painting a Fence
Problem
You need to hire some people to paint a fence. The fence is composed of 10000 contiguous sections, numbered from 1 to 10000.
You get some offers from painters to help paint the fence. Each painter offers to paint a contiguous subset of fence sections in a particular color. You need to accept a set of the offers, such that:
- Each section of the fence is painted.
- At most 3 colors are used to paint the fence.
If it is possible to satisfy these two requirements, find the minimum number of offers that you must accept.
Input
- One line containing an integer T, the number of test cases in the input file.
For each test case, there will be:
- One line containing an integer N, the number of offers.
- N lines, one for each offer, each containing "C A B" where C is the color, which is an uppercase string of up to 10 letters, A is the first section and B is the last section to be painted. 1 ≤ A ≤ B ≤ 10000.
Output
- T lines, one for each test case in the order they occur in the input file, each containing the string "Case #X: Y", where X is the case number, and Y is the number of offers that need to be accepted, or "Case #X: IMPOSSIBLE" if there is no acceptable set of offers.
Limits
1 ≤ T ≤ 50
Small dataset
1 ≤ N ≤ 10
Large dataset
1 ≤ N ≤ 300
Sample
Input |
Output |
5 |
Case #1: 2 |
枚舉顏色數+Greedy就可以了
Code:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int head[305];
typedef struct
{
int f;
int e;
int co;
int next;
}C;
C offer[305];
C ss[305];
int cmp(const void *a, const void *b)
{
C x = *((C*)a);
C y = *((C*)b);
if(x.f!=y.f)
return x.f-y.f;
return x.e-y.e;
}
int main(void)
{
map<string,int> color;
int T,N;
scanf("%d",&T);
int tc = 1;
int i,j,k;
char s[30];
int f,e;
int cn;
C tmp;
int on;
int tans;
while(T--)
{
scanf("%d",&N);
color.clear();
on =0;
memset(head,-1,sizeof(head));
cn = 1;
for(i=1;i<=N;i++)
{
scanf("%s %d %d",s,&f,&e);
string x(s);
if(color[x]==0)
{
color[x] = cn++;
}
offer[on].f = f;
offer[on].e = e;
offer[on].co = color[x];
offer[on].next = head[color[x]];
head[color[x]] = on++;
}
int ans = 1e8;
/*1*/
int l;
int sn = 0;
for(i=1;i<cn;i++)
{
sn = 0;
for(j=head[i];j!=-1;j=offer[j].next)
{
ss[sn++] = offer[j];
}
qsort(ss,sn,sizeof(ss[0]),cmp);
int cr = 0;
int cl = 0;
tans = 0;
for(j=0;j<sn;j++)
if(ss[j].f<=cr+1)
{
int j1 = j;
int tr = cr;
while(ss[j1].f<=cr+1&&j1<sn)
{
if(ss[j1].e>tr)
tr = ss[j1].e;
j1++;
}
if(tr>cr)
{
cr = tr;
cl = ss[j1-1].f;
tans ++;
}
j = j1-1;
}
if(cr>=10000&&tans<ans)
ans = tans;
}
/*2*/
for(i=1;i<cn;i++)
for(j=i+1;j<cn;j++)
{
sn = 0;
for(k=head[i];k!=-1;k=offer[k].next)
{
ss[sn++] = offer[k];
}
for(k=head[j];k!=-1;k=offer[k].next)
{
ss[sn++] = offer[k];
}
qsort(ss,sn,sizeof(ss[0]),cmp);
int cr = 0;
int cl = 0;
tans = 0;
for(k=0;k<sn;k++)
if(ss[k].f<=cr+1)
{
int k1 = k;
int tr = cr;
while(ss[k1].f<=cr+1&&k1<sn)
{
if(ss[k1].e>tr)
tr = ss[k1].e;
k1++;
}
if(tr>cr)
{
cr = tr;
cl = ss[k1-1].f;
tans ++;
}
k = k1-1;
}
if(cr>=10000&&tans<ans)
ans = tans;
}
/*3*/
for(i=1;i<=cn;i++)
for(j=i+1;j<=cn;j++)
for(k=j+1;k<=cn;k++)
{
sn = 0;
for(l=head[i];l!=-1;l = offer[l].next)
{
ss[sn++] = offer[l];
}
for(l=head[j];l!=-1;l = offer[l].next)
{
ss[sn++] = offer[l];
}
for(l=head[k];l!=-1;l = offer[l].next)
{
ss[sn++] = offer[l];
}
qsort(ss,sn,sizeof(ss[0]),cmp);
int cr = 0;
int cl = 0;
tans = 0;
for(l=0;l<sn;l++)
if(ss[l].f<=cr+1)
{
int l1 = l;
int tr = cr;
while(ss[l1].f<=cr+1&&l1<sn)
{
if(ss[l1].e>tr)
tr = ss[l1].e;
l1++;
}
if(tr>cr)
{
cr = tr;
cl = ss[l1-1].f;
tans ++;
}
l = l1-1;
}
if(cr>=10000&&tans<ans)
ans = tans;
}
printf("Case #%d: ",tc++);
if(ans==1e8)
printf("IMPOSSIBLE\n");
else
printf("%d\n",ans);
}
return 0;
}
全站熱搜
留言列表
