学步园

250pt:

题目：

Problem Statement
	Andrew drew a bunch of points on a sheet of graph paper. You are given the coordinates of these points in two vector <int>s: X and Y. That is, for each valid i, there is a point at the coordinates (X[i], Y[i]). Now Andrew wants to draw a rectangle. The sides of the rectangle must be parallel to the coordinate axes. (In other words, each side of the rectangle must be either horizontal or vertical.) Additionally, each of Andrew's points must be inside the rectangle or on its boundary. Return the area of the smallest possible rectangle Andrew can draw.
Definition
	Class: BoundingBox Method: smallestArea Parameters: vector <int>, vector <int> Returns: int Method signature: int smallestArea(vector <int> X, vector <int> Y) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 256
Constraints
-	X will have between 2 and 50 elements, inclusive.
-	X and Y will have the same number of elements.
-	Each element of X and Y will be between -100 and 100, inclusive.
-	The points described by X and Y will not be in a straight line horizontally or vertically. That is, the smallest rectangle will have a positive area.
Examples
0)
	{0,1} {1,0} Returns: 1
1)
	{0,-2,-1} {-1,-1,-2} Returns: 2
2)
	{0,0,1,0,-1,2} {0,1,2,-2,0,-1} Returns: 12
3)
	{9,-88,-40,98,-55,41,-38} {-65,56,-67,7,-58,33,68} Returns: 25110

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
    

分析：找出x之间差的最大值，y之间差的最大值即可

代码：

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class BoundingBox {
public:
	int smallestArea(vector <int>, vector <int>);
};

int BoundingBox::smallestArea(vector <int> X, vector <int> Y) {
	int xmax=-10000;
	int xmin = 10000;
	int ymax = -10000;
	int ymin = 10000;
	for(int i=0;i<X.size();i++)
	{
		xmax = max(X[i],xmax);
		xmin = min(X[i],xmin);
	}
	for(int i=0;i<Y.size();i++)
	{
		ymax = max(Y[i],ymax);
		ymin = min(Y[i],ymin);
	}
	return (xmax-xmin)*(ymax-ymin);
}


//Powered by [KawigiEdit] 2.0!

500pt：

题目：

{"a","a",""}

{"a"}

Returns: 6

{"zaz"}

{}

Returns: 4

{"top"}

{"coder"}

Returns: 8

{}

{"daata"}

Returns: 7

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
    

分析：如果暴力遍历的话，复杂度是N的三次，N=5000,明显复杂度太高，故用动态规划把复杂度降到N的平方

代码：

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class PalindromicSubstringsDiv2 {
public:
	int count(vector <string>, vector <string>);
};

int PalindromicSubstringsDiv2::count(vector <string> S1, vector <string> S2) {
	string s = "";
	for(int i=0;i<S1.size();i++)
		s+=S1[i];
	for(int i=0;i<S2.size();i++)
		s+=S2[i];
	int n = s.length();
	vector<vector<bool> > dp(n,vector<bool>(n,false));
	for(int len = 1;len<=n;len++)
	{
		for(int i=0;i<=n-len;i++)
		{
			int j = i+len-1;
			if(i==j)
				dp[i][j]=true;
			else if(j==i+1)
			{
				if(s[i]==s[j])
					dp[i][j]=true;
			}
			else if(dp[i+1][j-1]&&s[i]==s[j])
				dp[i][j]=true;
		}
	}
	int ret = 0;
	for(int i=0;i<n;i++)
		for(int j=i;j<n;j++)
			if(dp[i][j])
				ret++;
	return ret;
}


//Powered by [KawigiEdit] 2.0!

1000pt的不会做。。。。。。

终于再次爬回div1了。。。再接再厉！