首页 > ACM题库 > HDU-杭电 > HDU 2877-Florid Banner-动态规划-[解题报告]HOJ
2014
02-17

HDU 2877-Florid Banner-动态规划-[解题报告]HOJ

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:

题目描述:给定一个矩阵,只能一行一行构造,给定不同的串和构造使用的费用,问最小费用。

解法:dp+trie

本来是一个很傻逼的题目,但是一直过不去,最后发现原来是给定颜色是不一定是从0开始编号的,可能是随机的。。。。。我勒个去。。。

#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;
}
 
void add(int c,int l){
    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);
            add(c,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;
}

解题参考:http://hi.baidu.com/isaacpei/item/efdbf048702c6232fa89602a


  1. 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