`
java-mans
  • 浏览: 11710431 次
文章分类
社区版块
存档分类
最新评论

poj 1691 Painting A Board

 
阅读更多

题目链接:http://poj.org/problem?id=1691

题目思路:状态压缩dp水过。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int dp[1<<15][16];
int x1[16],x2[16],y1[16],y2[16],co[16],mp[16];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,i,j,k,tmp;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d%d%d",&y1[i],&x1[i],&y2[i],&x2[i],&co[i]);
        }
        memset(mp,0,sizeof(mp));
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(y2[j]!=y1[i]||x2[j]<=x1[i]||x1[j]>=x2[i])
                    continue;
                mp[i]+=(1<<j);
            }
        }
       // for(i=0;i<(1<<n);i++)
         //   dp[i][0]=0;
        for(i=0;i<(1<<n);i++)
            for(j=0;j<n;j++)
            {

                dp[i][j]=inf;
                if((i&(1<<j))!=0&&((i&mp[j])==mp[j]))
                {
                    tmp=i-(1<<j);
                    if(tmp==0)
                    {
                        dp[i][j]=1;
                        continue;
                    }
                    for(k=0;k<n;k++)
                    {
                        if((tmp&(1<<k))!=0&&((tmp&mp[k])==mp[k])&&dp[tmp][k]!=inf)
                        {
                            if(co[k]==co[j])
                            dp[i][j]=min(dp[i][j],dp[tmp][k]);
                            else
                            dp[i][j]=min(dp[i][j],dp[tmp][k]+1);
                        }
                    }
                }
            }
            int ans=inf;
            for(i=0;i<n;i++)
            {
                ans=min(ans,dp[(1<<n)-1][i]);
            }
            printf("%d\n",ans);
    }
}


分享到:
评论

相关推荐

    POJ1691-Painting A Board 【拓扑+DFS】

    【标题】"POJ1691-Painting A Board 【拓扑+DFS】"是一个源自北京大学在线编程平台POJ的编程题目,它主要涉及到图论中的拓扑排序和深度优先搜索(DFS)算法。该题目的核心是解决一个与涂色相关的实际问题,通过运用...

    POJ1691–Painting A Board 测试数据

    《POJ1691——绘画木板:测试数据解析》 编程竞赛是提升编程技能、锻炼思维能力的重要途径,而POJ(Problem Set of Peking University)则是其中的一个知名平台。在POJ1691这个题目中,我们需要解决的是“绘画木板...

    poj1691解题报告

    - **题目名称**:Painting A Board - **时间限制**:1S - **内存限制**:1000K - **提交总数**:62 - **通过总数**:35 - **来源**:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691)...

    状态压缩DP.pdf

    #### 例题:POJ1691 Painting A Board 在这个问题中,我们需要给一块木板的不同区域涂上颜色。可以定义状态为已涂色的区域和当前使用的颜色。状态转移的过程就是将尚未涂色的区域染成当前的颜色或更换颜色。 #### ...

    poj 3363 Annoying painting tool.md

    poj 3363 Annoying painting tool.md

    POJ1584-A Round Peg in a Ground Hole

    【标题】"POJ1584-A Round Peg in a Ground Hole" 是一道来自北京大学在线判题系统POJ(Problem Set)的经典算法题目。这道题目主要涉及的是几何计算和位运算的应用,属于计算机科学中的基础算法问题。 【描述】...

    POJ2488-A Knight's Journey【骑士游历】

    【标题】"POJ2488-A Knight's Journey【骑士游历】" 【知识点解析】 本题是来自北京大学在线编程平台POJ的一道经典算法题——“骑士游历”。题目要求解决的是一个典型的图论问题,即在国际象棋棋盘上,骑士能否...

    POJ1942-Paths on a Grid

    【标题】"POJ1942-Paths on a Grid"是北京大学在线编程平台POJ上的一道经典算法题目,其主要目标是探索在网格上行走的路径问题。 【描述】该题目的描述中提到“解题报告+AC代码”,这暗示了解决此问题的关键在于...

    poj题目分类

    * 记忆化搜索:例如 poj3373、poj1691。 5. 动态规划: * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列...

    POJ1005-I Think I Need a Houseboat

    【标题】"POJ1005-I Think I Need a Houseboat" 是一个编程竞赛题目,源自北京大学的在线评测系统POJ(Problem Set of Peking University)。这个题目旨在考验参赛者的算法设计和实现能力,主要涉及数据结构和动态...

    POJ2031-Building a Space Station【Prim+计算几何】

    【标题】"POJ2031-Building a Space Station【Prim+计算几何】"是一道编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目结合了图论中的Prim算法与计算几何领域的知识,挑战参赛者的算法...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    poj训练计划.doc

    根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    acm训练计划(poj的题)

    - (poj3373, poj1691):针对特定问题的状态压缩变形。 ### 十一、进阶动态规划 1. **自定义动态规划**: - 针对特定问题设计动态规划模型。 2. **扩展动态规划**: - (POJ3254, poj2411, poj1185):将传统动态...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

Global site tag (gtag.js) - Google Analytics