5.11 算法课程OJ

本专题用于记录算法设计与分析课程中的习题。

一道简单的dp问题
用时8m10s

 


#include

using namespace std;

const int N=10;

int dp[N][N];
int n;

int main(){
	cin>>n;	
	
	//走一次 
	for(int j=1;j<=6;j++){
		dp[1][j]=1; 
	}
	
	//每次至少走一步，因此最多n次 
	for (int i=2;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=6;k++)
			  if((j-k)>0)
				dp[i][j]+=dp[i-1][j-k]; 
		}
	}	
	
	int ans=0;
	
	for(int i=1;i<=n;i++){
		ans+=dp[i][n];
	}
	
	cout< 
电池的寿命 
 
 
 
用时：16m49s
 看着无从下手，实际上，分类讨论
 
 
0个或者1个电池当然是0
2个电池没法组合，取小的那个
3个以上电池，总是可以找到一种方式使得所有电池都被完全使用。
 证明
 对于三个电池，一定有a+b>=c成立（可通过改变abc顺序实现）那么此时一定可以找到一个x使得（a-x+b-x）= c 这样的话，在a,b都用完x时间后和c组合，就可以完全使用电池。
 对于四个电池，一定可以通过先使用两个电池的方法耗尽其中一个，接着又回到三个电池的情况，因此可以完全使用电池
 以此类推，无论多少种，只要n>=3,电池都可以完全使用
 证毕
 
 
#include
#include

using namespace std;

const int N= 1100;
int n;
double a[N];

int main(){
	
	while(scanf("%d",&n)!=EOF){
		
		double sum=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sum+=a[i];
		}
		
		if(n==0||n==1)
			printf("%.1fn",0);	
		
		else if (n==2){
			double minm=min(a[1],a[2]);
			printf("%.1fn",minm);	
		}
			
		else
			printf("%.1fn",sum/2);	
	}
	
	return 0;
}