poj 1185趣味はやはり堅持しなければなりません.の

いつの間にか、私が興味を持っているアルゴリズムをなくして、ブログを更新していません.しかし、この时間、いつも生活の中で何かが少なくなったような気がして、よく慣れていないような気がします.私はアルゴリズムの勉強とブログを書くことを何ヶ月も冷遇しました.良い習慣はずっと続けなければならないし、自分が正しいと思っている習慣を堅持してほしい.このように生きてこそおもしろいですね.
 
/*************************************************************************************************************************************************************************************************************************************後で他の人の解題報告を参考にして知った.f[i][j][k]=max{f[i-1][k][l]+c[j]}*うちf[i][j][k]はi行目がs[j]i-1行目がs[k]のときに兵士の最大*値を置くことができることを示す.そしてjを列挙するだけでいい.状態が多いように見えますが、実際には1行あたり60種類以上あります.*したがってj<60,k<60である.毎回2行しか必要ないので、iはスクロール配列を使うことができます.i<2.*************************************/
ここではスクロール配列を使いましたが、実際にはf[101][61][61]を直接開いてもいいので、スクロール配列を使わなくてもいいのですが、メモリスペースは多く使われています.
 
 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char map[101][11];
int origMap[101], row,num, col, s[61], c[61], f[2][61][61];

int main()
{
	memset(origMap, 0, sizeof(origMap));
	memset(s, 0, sizeof(s));
	memset(c, 0, sizeof(c));
	scanf("%d %d", &row, &col);
	//getchar();
	for (int i = 0; i < row; ++ i)
	{
		scanf("%s", map[i]);
	}
	for (int i = 0; i < row; ++ i)
	{
		for (int j = 0; j < col; ++ j)
		{
			//scanf("%c", & map[i][j]);
			if (map[i][j] == 'H')
			{
				origMap[i] += (1 << j);//    ，     1
			}
		}
		//getchar();
	}
	num = 0;

         //         
	for (int k = 0; k < (1 << col); ++ k)
	{
		int m = k;
		if (((m << 1) & k) || ((m << 2) & k))
		{
			continue;
		}
		c[num] = m % 2;
		while (m = (m >> 1))
		{
			c[num] += m % 2;
		}
		s[num ++ ] = k;
	}

	int roll = 0;
	for (int i = 0; i < row; ++ i)
	{
		for (int j = 0; j < num; ++ j)
		{
			if (s[j] & origMap[i])// i  j             
			{
				continue;
			}
			if (i == 0)
			{
				f[roll][j][0] = c[j];
			}
			else if (i == 1)
			{
				for (int k = 0; k < num; ++ k)
				{
					if (s[k] & origMap[i - 1])//i-1     
					{
						continue;
					}
					if (s[j] & s[k])//i  i-1     
					{
						continue;
					}
					if (f[roll][j][k] < f[(roll + 1) % 2][k][0] + c[j])
					{
						f[roll][j][k] = f[(roll + 1) % 2][k][0] + c[j];
					}
				}
			}
			else
			{
				for (int k = 0; k < num; ++ k)
				{
					if (s[k] & origMap[i - 1])
					{
						continue;
					}
					if (s[j] & s[k])
					{
						continue;
					}
					for (int l = 0; l < num; ++ l)
					{
						if (s[l] & origMap[i - 2])
						{
							continue;
						}
						if ((s[k] & s[l]) | (s[j] & s[l]))
						{
							continue;
						}
						if ( f[roll][j][k] < f[(roll + 1) % 2][k][l] + c[j] )
						{
							f[roll][j][k] = f[(roll + 1) % 2][k][l] + c[j];
						}
					}
				}
			}
		}
		roll = (roll + 1) % 2;
	}
	roll = (roll + 1) % 2;
         //     
	int mMax = 0;
	for (int i = 0; i < num; ++ i)
	{
		for (int j = 0; j < num; ++ j)
		{
			if (mMax < f[roll][i][j])
			{
				mMax = f[roll][i][j];
			}
		}
	}

	printf("%d
", mMax);
	return 0;
}