[usaco]3.4.4 变形的动态规划问题Electric Fence

Electric Fence
Don Piele
In this problem, `lattice points' in the plane are points with integer coordinates.

In order to contain his cows, Farmer John constructs a triangular electric fence by stringing a "hot" wire from the origin (0,0) to a lattice point [n,m] (0<=;n<32000, 0<m<32000), then to a lattice point on the positive x axis [p,0] (p>0), and then back to the origin (0,0).

A cow can be placed at each lattice point within the fence without touching the fence (very thin cows). Cows can not be placed on lattice points that the fence touches. How many cows can a given fence hold?

PROGRAM NAME: fence9
INPUT FORMAT
The single input line contains three space-separated integers that denote n, m, and p.

SAMPLE INPUT (file fence9.in)
7 5 10

OUTPUT FORMAT
A single line with a single integer that represents the number of cows the specified fence can hold.

SAMPLE OUTPUT (file fence9.out)
20

------------------------------------------------
这是个经过变形的动态规划问题：
在常规的动态规划的基础上加上一个条件：
如果加上某个音乐后，这个disk会爆掉的话，那么就增加一个新的disk。
我的解法：
----------------------------------------------------

/*
ID:yunleis2
PROG:rockers
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<iomanip>
const int MAXN=20;
const int MAXT=20;
const int MAXM=20;

using namespace std;
int dp[MAXN+1][MAXM*MAXT+1];
bool exist[MAXN+1][MAXM*MAXT+1];
int song[MAXN+1];
int n,t,m;
#define MAX(X,Y) (X>Y?X:Y)
int main()
{
	fstream fin("rockers.in",ios::in );
	fin>>n>>t>>m;
	for(int i=0;i<n;i++){
		dp[i][0]=0;
		fin>>song[i];
	}
	dp[n][0]=0; 
	for(int i=0;i<=n;i++){
		for(int j=0;j<=(n*t+1);j++){
			exist[i][j]=false;
		}
	}
	exist[0][0]=true;
	for(int i=0;i<n;i++){
		for(int j=0;j<=(m*t);j++){
			if(exist[i][j]){
				exist[i+1][j]=true;
				dp[i+1][j]=MAX(dp[i][j],dp[i+1][j]);
				if(song[i]<=t){
					if((j+song[i])%t==0){
						exist[i+1][j+song[i]]=true;
						dp[i+1][j+song[i]]=MAX(dp[i][j]+1,dp[i+1][j+song[i]]);
					}
					else if(j!=0&&(j-1)/t!=((j-1)+song[i])/t){
						int T=(1+(j-1)/t)*t;
						T+=song[i];
						exist[i+1][T]=true;
						dp[i+1][T]=MAX(dp[i][j]+1,dp[i+1][T]);
					}
					else{
						exist[i+1][j+song[i]]=true;
						dp[i+1][j+song[i]]=MAX(dp[i][j]+1,dp[i+1][j+song[i]]);
					}
				}
			}
		}
	}
#if 0
	for(int j=0;j<=(m*t);j++)
		cout<<setw(2)<<j<<" ";
	cout<<endl;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=(m*t);j++){
			cout<<setw(2)<<dp[i][j]<<" ";
		}
		cout<<endl;
	}
#endif
	int result=0;
	for(int i=m*t;i>=0;i--){
		if(exist[n][i])
		{
			if(dp[n][i]>result)
				result=dp[n][i];
			 
		}
	}
	fstream fout("rockers.out",ios::out);
	fout<<result<<endl;
	//system("pause");
}