2014
02-17

# Florid Banner

Adam C. Murphy loves shopping. One day, when he was wandering along the avenue, he discovered several stores with florid banners. (A 2*5 example is shown below)

He found them fantastic and decided to get one in order to decorate his fresh new house. Unfortunately, no one meets Adam’s requirement, after visiting all stores nearby. What was worse, all banners left in the stores only have width 1. So he decided to make one himself by sewing them together.
Adam wants to make a banner exactly as he designed. He didn’t want to flip or rotate the materials he had, since he believed that keep it in its original way is more beautiful. And he didn’t want to cut the banners for the same reason.
Each material had different prices, so he wants to make his florid banner with minimum cost.

The input consists of one or more test cases.
Each test case contains two parts.
The first part of the input describes the banner Mr. Murphy designed.
First line:
Two integers M (0<M<=10) and N (0<N<=10,000), describes the width and the length of the banner.

Second line:
One integer t states that the banner has t regions.

Following t lines:
Each line has 5 integers x1,y1,x2,y2,c, represents a region from (x1,y1), the left bottom corner, to (x2,y2), the right top corner, and the color type of this region is c.
The whole banner is M*N, with its left bottom located at (0, 0). It is guaranteed that t regions can exactly cover the whole banner once. (0<=x1<x2<=M, 0<=y1<y2<=N)

The second part describes the materials left in the store. No need to worry about the number of them, because they are infinity.
The first line:
The number of materials fn(0<=fn<=10000)

Following fn lines:
Each line represents one kind of material. Following an integer P(P>0) indicates the price, and an integer L(1<=L<=20) indicates the length of this banner. Then L integers for this material, i-th number indicates the color at position range from (0,i-1) to (1,i).

You may assume that the number of colors is no more than 30.
Input will be terminated by EOF.

The input consists of one or more test cases.
Each test case contains two parts.
The first part of the input describes the banner Mr. Murphy designed.
First line:
Two integers M (0<M<=10) and N (0<N<=10,000), describes the width and the length of the banner.

Second line:
One integer t states that the banner has t regions.

Following t lines:
Each line has 5 integers x1,y1,x2,y2,c, represents a region from (x1,y1), the left bottom corner, to (x2,y2), the right top corner, and the color type of this region is c.
The whole banner is M*N, with its left bottom located at (0, 0). It is guaranteed that t regions can exactly cover the whole banner once. (0<=x1<x2<=M, 0<=y1<y2<=N)

The second part describes the materials left in the store. No need to worry about the number of them, because they are infinity.
The first line:
The number of materials fn(0<=fn<=10000)

Following fn lines:
Each line represents one kind of material. Following an integer P(P>0) indicates the price, and an integer L(1<=L<=20) indicates the length of this banner. Then L integers for this material, i-th number indicates the color at position range from (0,i-1) to (1,i).

You may assume that the number of colors is no more than 30.
Input will be terminated by EOF.

2 5
7
0 0 2 1 0
1 1 2 3 0
0 1 1 2 1
0 2 1 3 2
0 3 2 4 1
0 4 1 5 3
1 4 2 5 2
5
1 3 0 0 0
2 3 2 1 3
2 3 0 1 2
1 2 1 3
5 1 0

15
Hint
Hint

The pattern of the sample is as follows:



#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;

const int INF=0x3f3f3f3f;
typedef long long ll;
const int M=10005;
const int mod=1e9+7;
const double eps=1e-6;
const double Pi=2*acos(0.0);

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline int bit(int x){return 1<<x;}
inline double dabs(double x){return x>0?x:(-x);}
inline int abs(int x){return x>0?x:(-x);}
inline int lowbit(int x){return x&(-x);}

int t,n,m,tail;
short ma[12][10010];
int dp[10010],color[30],cnt;
struct node{
int next[30],val;
}trie[180000];

void init(){
tail=1;
cnt=0;
memset(trie,-1,sizeof(trie));
}

int find(int num){
for(int i=0;i<cnt;i++)
if(color[i]==num)
return i;
color[cnt++]=num;
return cnt-1;
}

int now=0,tmp;
for(int i=0;i<l;i++){
scanf("%d",&tmp);
tmp=find(tmp);
if(trie[now].next[tmp]==-1)
trie[now].next[tmp]=tail++;
now=trie[now].next[tmp];
}
if(trie[now].val==-1)
trie[now].val=c;
else
trie[now].val=min(trie[now].val,c);
}

void getdp(int x){
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(int i=1;i<=m;i++){
if(dp[i-1]==-1) continue;
int tmp=trie[0].next[ma[x][i]],j=i;
while(tmp!=-1&&j<=m){
if(trie[tmp].val!=-1){
if(dp[j]==-1)
dp[j]=dp[i-1]+trie[tmp].val;
else
dp[j]=min(dp[j],dp[i-1]+trie[tmp].val);
}
tmp=trie[tmp].next[ma[x][++j]];
}
}
}

int main(){
int x1,x2,y1,y2,c,l;
while(~scanf("%d %d",&n,&m)){
init();
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
c=find(c);
for(int i=x1;i<x2;i++)
for(int j=y1;j<y2;j++)
ma[i][j+1]=c;
}
scanf("%d",&t);
while(t--){
scanf("%d",&c);
scanf("%d",&l);
}
int ans=0;
bool jud=0;
for(int i=0;i<n;i++){
getdp(i);
ans+=dp[m];
if(dp[m]<0) {
jud=1;
break;
}
}
if(jud) puts("impossible");
else printf("%d\n",ans);
}
return 0;
}

1. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

2. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

3. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

4. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

5. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

6. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

7. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

8. 这位“猫耳朵”的答主，你可以多看看他在其他动漫题里的回答，偏主观，他能在这边说“富坚能用最简单的线条把一个画面表达完美，说明他dio”，然后在另一边却说着反话，只是把画家的名字换了，https://www.zhihu.com/question/30263

9. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience