亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

UVA - 10118Free Candies(記憶化搜索)

系統 1835 0

題目:UVA - 10118Free Candies(記憶化搜索)


題目大意:給你四堆糖果,每一個糖果都有顏色。每次你都僅僅能拿隨意一堆最上面的糖果,放到自己的籃子里。假設有兩個糖果顏色同樣的話,就行將這對糖果放進自己的口袋。自己的籃子最多僅僅能裝5個糖果,假設滿了,游戲就結束了。問你可以得到的最多的糖果對數。


解題思路:這題想了好久,好不easy把狀態想對了,結果腦子發熱,又偏離了方向。dp【a】【b】【c】【d】:四堆糖果如今在最上面的是哪一個。由于以下的糖果假設確定了,那么接下了無論你怎么取,最優的肯定是僅僅有一種。所以能夠把如今剩余的糖果的最多數量加上你之前取的那些糖果你能得到的糖果最多數量,就是要求的最多的糖果對數。

dp【a】【b】【c】【d】 = Max(dp【a + 1】【b】【c】【d】 + 0|1, dp[a][b +1】【c】【d】 + 0|1, dp【a】【b】【c + 1】【d】 + 0|1 , dp【a】【b】【c】【d ?+1] + 0|1).0 | 1取決于你如今籃子里是否有和我取的那個糖果顏色同樣的。相應的籃子里的糖果數量要變化。假設數量等于5了,就說明不能放了,返回0.而且每堆糖果都有最大的數量,取完也是要結束的。這些邊界條件要注意.這里發現了一個新的知識:用memcpy的時候假設不是里面的全部數據都要的話,要指明長度,不然可能會出現錯誤。


代碼:

      #include <cstdio>
#include <cstring>

const int N = 42;
const int M = 5;
const int maxn = 1000005;

int candy[N][M];
int top[M];//存放每堆糖果最上面的序號
int f[N][N][N][N];
int n;

int Max (const int a, const int b) { return a > b ? a: b; }

void init () {

	memset (f, -1, sizeof (f));
	f[n][n][n][n] = 0;//結束狀態不論籃子滿不滿
}

bool handle (int r, int c, int k, int *b) {//處理是否有同樣的塘果 int *b是籃子,k + 1是里面有的糖果的個數。

	int i;
	for (i = 0; i < k; i++) {

		if (candy[r][c] == b[i])
			break;
	}

	if (!k || i == k) {
		b[k] = candy[r][c];
		return false;
	} else {

		for (int j = i; j < k - 1; j++)
			b[j] = b[j + 1];
		return true;
	}
}

int dfs (int k, int *bket, int a, int b, int c, int d) {

	int bket1[M * 2];
	int& ans = f[a][b][c][d];
	if (k >= M)//籃子滿了
		return 0;//注意這里ans不一定等于0,由于取糖果的順序不同的話,這個籃子的情況可能不同
	if (ans != -1)
		return ans;
	top[1] = a;
	top[2] = b;
	top[3] = c;
	top[4] = d;
	for (int i = 1; i < M; i++) {

		/*for (int j = 0; j < k; j++)
			bket1[j] = bket[j];*/
		memcpy (bket1, bket, k * sizeof (int));//注意
		/*for (int j = 0; j < k; j++)
			printf ("%d ", bket1[j]);
		printf ("\n");*/
		if (handle (top[i], i, k, bket1)) {

			top[i]++;
			if (top[i] <= n)
				ans = Max (ans, dfs (k - 1, bket1, top[1], top[2], top[3], top[4]) + 1);				
		} else {

			top[i]++;
			if (top[i] <= n)
				ans = Max (ans, dfs (k + 1, bket1, top[1], top[2], top[3], top[4]));
		}
		top[i]--;
	}
	return ans;
}

int main () {

	while (scanf ("%d", &n), n) {

		for (int i = 0; i < n; i++)
			for (int j = 1; j < M; j++)
				scanf ("%d", &candy[i][j]);

		int b[M * 2];
		init ();
		printf ("%d\n", dfs (0, b, 0, 0, 0, 0));
//		printf ("%d\n", f[n][n - 1][0][0]);
/*		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					for (int l = 0; l < n; l++) 
						printf ("%d ", f[i][j][k][l]);
					printf ("\n");
				}
				printf ("\n");
			}
			printf ("\n");
		}
		printf ("\n");*/
	}
	return 0;
}
    


UVA - 10118Free Candies(記憶化搜索)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。。?/p>

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 色中色污| 青青久久99久久99久久999 | 午夜精品成年片色多多 | 理论片 我不卡影院 | 97精品国产高清在线看入口 | 国产一区二区三区免费在线观看 | 普通话对白国产情侣自啪 | 国产精品呦呦 | 最新永久地址 | 国产99热在线观看 | 日韩欧美伊人久久大香线蕉 | 99久久99久久久精品齐齐鬼色 | 免费一级特黄视频 | 午夜一级毛片 | 久草美女 | 国产精品成人麻豆专区 | 岛国大片免费在线观看 | 日日狠狠久久偷偷四色综合免费 | 伊人爱爱网 | 深夜福利在线免费观看 | 亚洲国产另类久久久精品小说 | 国产亚洲综合成人91精品 | 国产精品爱久久久久久久 | 亚洲欧美日韩v中文在线 | 奇米影视778成人四色狠狠 | 在线免费观看中文字幕 | 精品一区二区三区免费毛片爱 | 夜夜爱夜夜爽夜夜做夜夜欢 | 久久动漫精品 | 亚洲精品一区二区不卡 | 国产伊人久久 | 热久久99精品这里有精品 | 国产欧美综合精品一区二区 | 欧美一区二区三区播放 | 毛片在线观看网站 | 99秒拍福利大尺度视频 | 久久频| 性生活国产 | 一级韩国aa毛片免费观看 | 99热精品在线 | 国产真实乱子伦精品 |