题目链接: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】"是一个源自北京大学在线编程平台POJ的编程题目,它主要涉及到图论中的拓扑排序和深度优先搜索(DFS)算法。该题目的核心是解决一个与涂色相关的实际问题,通过运用...
《POJ1691——绘画木板:测试数据解析》 编程竞赛是提升编程技能、锻炼思维能力的重要途径,而POJ(Problem Set of Peking University)则是其中的一个知名平台。在POJ1691这个题目中,我们需要解决的是“绘画木板...
- **题目名称**:Painting A Board - **时间限制**:1S - **内存限制**:1000K - **提交总数**:62 - **通过总数**:35 - **来源**:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691)...
#### 例题:POJ1691 Painting A Board 在这个问题中,我们需要给一块木板的不同区域涂上颜色。可以定义状态为已涂色的区域和当前使用的颜色。状态转移的过程就是将尚未涂色的区域染成当前的颜色或更换颜色。 #### ...
poj 3363 Annoying painting tool.md
【标题】"POJ1584-A Round Peg in a Ground Hole" 是一道来自北京大学在线判题系统POJ(Problem Set)的经典算法题目。这道题目主要涉及的是几何计算和位运算的应用,属于计算机科学中的基础算法问题。 【描述】...
【标题】"POJ2488-A Knight's Journey【骑士游历】" 【知识点解析】 本题是来自北京大学在线编程平台POJ的一道经典算法题——“骑士游历”。题目要求解决的是一个典型的图论问题,即在国际象棋棋盘上,骑士能否...
【标题】"POJ1942-Paths on a Grid"是北京大学在线编程平台POJ上的一道经典算法题目,其主要目标是探索在网格上行走的路径问题。 【描述】该题目的描述中提到“解题报告+AC代码”,这暗示了解决此问题的关键在于...
* 记忆化搜索:例如 poj3373、poj1691。 5. 动态规划: * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列...
【标题】"POJ1005-I Think I Need a Houseboat" 是一个编程竞赛题目,源自北京大学的在线评测系统POJ(Problem Set of Peking University)。这个题目旨在考验参赛者的算法设计和实现能力,主要涉及数据结构和动态...
【标题】"POJ2031-Building a Space Station【Prim+计算几何】"是一道编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目结合了图论中的Prim算法与计算几何领域的知识,挑战参赛者的算法...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
- (poj3373, poj1691):针对特定问题的状态压缩变形。 ### 十一、进阶动态规划 1. **自定义动态规划**: - 针对特定问题设计动态规划模型。 2. **扩展动态规划**: - (POJ3254, poj2411, poj1185):将传统动态...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...