poj_3176Cow Bowling问题(已解决)

Cow Bowling

Time Limit:1000MS		Memory Limit:65536K
Total Submissions:11089		Accepted:7256

Description

The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:

          7



        3   8



      8   1   0



    2   7   4   4



  4   5   2   6   5

Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame.

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output

Line 1: The largest sum achievable using the traversal rules

Sample Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

Hint

Explanation of the sample:

          7

         *

        3   8

       *

      8   1   0

       *

    2   7   4   4

       *

  4   5   2   6   5

The highest score is achievable by traversing the cows as shown above.

数塔问题！！！

和1163一样，测试了N久随机数据，可是就是wa，希望有人解答。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;

int maps[355][355];
int Hash[355][355];
int n;

void DFS(int x, int y)
{
	if(x == n) return;
	for(int i=0;i<=1;i++)
	{
		int p = x + 1;
		int q = y + i;
		if(p>=q && maps[p][q] + Hash[x][y] > Hash[p][q])
		{
			Hash[p][q] = maps[p][q] + Hash[x][y];
			DFS(p,q);
		}
	}
}

int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	memset(maps,0,sizeof(maps));
	memset(Hash,0,sizeof(Hash));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			scanf("%d",&maps[i][j]);
		}
	}
	Hash[1][1] = maps[1][1];
	DFS(1,1);
	int sum = maps[1][1];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			sum = max(sum,Hash[i][j]);
			//printf("hash[%d][%d] = %d\n",i,j,Hash[i][j]);
		}
	}
	printf("%d\n",sum);
	printf("Time used = %.2lf\n",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}

测试数据：

http://contest.usaco.org/DEC05_4.htm

一组铁定超时，我们不再考虑，引起错误的是150行0的那组测试数据，里面有个1.

Hash 数组memset初始化有问题，初始化为-1则所有结果正确。。。

此题的解决方法已经写出，不外乎记忆化搜索，DP。。。。

另附菜菜的随机测试代码：

#include <iostream>
#include <ctime>
#include <cstdio>
#include <windows.h>
using namespace std;
int main()
{
	while(1)
	{
		FILE *fp;
		fp = fopen("E:\\ACM\\POJ\\poj_3176\\in.txt","w");
		int n;
		srand(time(NULL));
		n = rand()%100;
		fprintf(fp,"%d\n",n);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
				fprintf(fp,"%d ",rand() % 100);
			}
			fprintf(fp,"\n");
		}
		fclose(fp);
		Sleep(5000);
		system("type in.txt");
		system("type.bat");
	}
	
    return 0;
}
 

type.bat

:

@type in.txt|1.exe
@1.exe<in.txt>>out1.txt
@type in.txt|2.exe
@2.exe<in.txt>>out2.txt

递归版本：

#include <iostream>
#include <cstring>
using namespace std;

int maps[355][355];
int vis[355][355];
int n;

int DFS(int x, int y)
{
	return vis[x][y] = maps[x][y] + ( x==n ? 0 : DFS(x+1,y) > DFS(x+1,y+1) ? DFS(x+1,y):DFS(x+1,y+1));
}

int main()
{
	freopen("in.txt","r",stdin);
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			cin>>maps[i][j];
		}
	}
	cout<<DFS(1,1)<<endl;
}

初学动态规划：

自下而上，

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int maps[355][355];
int vis[355][355];

int main()
{
	freopen("in.txt","r",stdin);
	int i, j;
	cin >> n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			cin >> maps[i][j];
		}
	}

	for(j=1;j<=n;j++)
		vis[n][j] = maps[n][j];
	for(i=n;i>=1;i--)
	{
		for(j=1;j<=i;j++)
		{
			vis[i][j] = maps[i][j] + max(vis[i+1][j],vis[i+1][j+1]);
		}
	}
	cout<<vis[1][1]<<endl;


}

记忆化搜索：

#include <iostream>
#include<cstring>
using namespace std;

int maps[355][355];
int vis[355][355];
int n;

int DFS(int x, int y)
{
	if(vis[x][y]>=0) return vis[x][y];
	return vis[x][y] = maps[x][y] + (x == n ? 0 : DFS(x+1,y) > DFS(x+1,y+1) ? DFS(x+1,y) : DFS(x+1,y+1));
}

int main()
{
	freopen("in.txt","r",stdin);
	int i,j;
	memset(vis,-1,sizeof(vis));
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			cin>>maps[i][j];
		}
	}
	cout<<DFS(1,1)<<endl;
	return 0;
}