228      技術社區[雲棲]

[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");
}

最後更新：2017-04-02 06:51:53

  上一篇： java定時器的具體使用和web使用

  下一篇： preferenceActivity和preferencescreen用法