UVa 11270 – Tiling Dominoes

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2245

這一題是插頭DP，而狀態轉移的方式和上一題不太一樣，這裡是「當前狀態」轉移到「後來狀態」，上一題則是「當前狀態」由「之前狀態」轉移過來。

關於插頭DP的說明，請參考此篇:

https://timbian.wordpress.com/2015/02/13/zerojudge-a228-%E5%B0%B1%E5%B0%91%E4%B8%80%E5%80%8B%E6%8F%92%E5%BA%A7%E7%94%A8%E5%BE%88%E4%B8%8D%E6%96%B9%E4%BE%BF/

 

/*
插頭DP，或輪廓線DP
http://mypaper.pchome.com.tw/zerojudge/post/1325083578

骨牌跟骨牌間的空隙即是有插頭的地方。 

考慮放直立的骨牌的話，則上方必為空格。
考慮放橫躺的骨牌的話，則左方必為空格，而上方必不為空格，否則不能填滿。
考慮不放的話，則上方必不為空格，否則不能填滿。 

*/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
	int n, m;

	while(scanf("%d %d", &n, &m) == 2)
	{
		if(n < m) swap(n, m);

		long long int dp[2][1 << 10] = {}; //滾動陣列
		int now = 0, pre = 1;
		int ALL = (1<<m)-1;

		dp[now][ALL] = 1;

		for(int i = 0; i < n; i ++)
		{
			for(int j = 0; j < m; j ++)
			{
				swap(now, pre);
				memset(dp[now], 0, sizeof(dp[now]));

				for(int k = 0; k <= ALL; k ++)
				{
					int left, up;
					/*
						這題中，輪廓線右、下插頭的狀況一樣，
						要嘛就都有，不然就都沒有，
						所以用位元表示時，直接省略輪廓線直的那條線。 

						            │
									│
                                一一
                	*/
					if(j == 0) left = 1;
					else left = k&(1<<(j-1)); 

					up = k&(1<<j);

					if(up == 0) //放直立的骨牌
					{
						dp[now][k^(1<<j)] += dp[pre][k];
					}
					if(up != 0 && left == 0) //放橫躺的骨牌
					{
						dp[now][k^(1<<(j-1))] += dp[pre][k];
					}
					if(up != 0) //不放，留空格
					{
						dp[now][k^(1<<j)] += dp[pre][k];
					}
				}
			}
		}
		printf("%lld\n", dp[now][ALL]);
	}	

	return 0;
}

Zerojudge a228: 就少一個插座用很不方便

題目來源:

http://zerojudge.tw/ShowProblem?problemid=a228

http://acm.hdu.edu.cn/showproblem.php?pid=1693

題目大意:

在n*m的地圖中，有些格子有樹，没有樹的格子不能到達，找一條或多條迴路，吃完所有的樹，求有多少種方法。

解題心得:

這是我第一次接觸插頭DP，也有人稱作輪廓線DP，我花了幾個小時才弄懂，因此特別寫下我的心得。

輪廓線表示的是當下插頭的狀態。如果兩個格子間有插頭，即代表兩個格子相連
，反之亦然。換句話說，輪廓線記錄在這條線兩邊的格子的關係。

這題顯然一個格子要嘛有兩個插頭(經過這個格子)，要嘛沒有插頭(不經過這個格子)。
因為迴路上每一個格子各有一進一出，且不可斜著走。

我們用1表示有插頭，0表示沒有插頭。而圖中綠線為插頭，紅線為當下的輪廓線，虛線則是上一個輪廓線，叉叉(第二列第三格)為當下決策的格子。

以下分三種情況來討論:

Zerojudge d591: D. 阿里不達轟!!

http://zerojudge.tw/ShowProblem?problemid=d591

因為炸彈數很少，所以直接暴力搜索，詳情請看Code

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

const int MAXM = 20, MAXN = 10;
const int INF = 1000000;

struct Element
{
	int x, y, r;
};

Element bomb[MAXM];
Element enemy[MAXN];
int cover[MAXM];
int M, N;
int ALL;

bool in_range(const Element& B, const Element& E)
{
	int distance = (B.x - E.x) * (B.x - E.x) + (B.y - E.y) * (B.y - E.y);
	int radius_sum = (B.r + E.r) * (B.r + E.r);
	return distance <= radius_sum;
}

void init()
{
	cin >> M >> N;
	
	ALL = (1 << N) - 1;	
	for(int i = 0; i < M; i ++)
		cin >> bomb[i].x >> bomb[i].y >> bomb[i].r;
	for(int i = 0; i < N; i ++)
		cin >> enemy[i].x >> enemy[i].y >> enemy[i].r;
	
	fill(cover, cover + M, 0);
	
	for(int i = 0; i < M; i ++)
		for(int j = 0; j < N; j ++)
			if(in_range(bomb[i], enemy[j]))
				cover[i] |= (1 << j);
}

int DFS(int now, int cnt, int range)
{
	if(now == M)
	{
		if(range == ALL) 
			return cnt;
		else
			return INF;
	}
	
	int num1 = DFS(now + 1, cnt, range); 
	
	range |= cover[now];
	int num2 = DFS(now + 1, cnt + 1, range);
	
	return min(num1, num2);
}

void solve()
{	
	int bombs = DFS(0, 0, 0);
	
	if(bombs == INF)
		cout << "Impossible";
	else
		cout << bombs;
		
	cout << "\n";
}


int main()
{
	int T;

	cin >> T;
	while(T--)
	{	
		init();
		solve();
	}
	
	return 0;
}

UVa 11825 – Hackers’ Crackdown

最近在學bitmask、狀態壓縮之類的東西，而這題花了我好多心力才看懂啊!網路上的教學文也都看得霧煞煞@.@，所以決定寫一篇心得，希望大家看得懂~~~

題目來源 :

按一下以存取 11825.pdf

參考資料 :
http://blog.csdn.net/keshuai19940722/article/details/19346211
http://www.cnblogs.com/acm-bingzi/p/3272898.html

題目大意 :

有一個包含n台電腦的系統，一共有n種服務，每台電腦都運行著這n種服務。你是一個駭客，對於每台電腦，你都可以選擇一項服務，使這台電腦和所有與它相臨的電腦終止該服務。當我們說一種服務癱瘓，則意味著這n台電腦中，已沒有任何一台可提供該服務，你的任務即是讓系統中愈多的服務癱瘓。