5.11 算法课程OJ

前言

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

求解掷色子游戏问题

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

/*
本题是一个dp问题
 
设dp[i][j]为第i次时走了j步的方案数 
 
*/ 


#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<<ans;
	
	return 0;
}

电池的寿命

用时：16m49s
看着无从下手，实际上，分类讨论

1. 0个或者1个电池当然是0
2. 2个电池没法组合，取小的那个
3. 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("%.1f\n",0);	
		
		else if (n==2){
			double minm=min(a[1],a[2]);
			printf("%.1f\n",minm);	
		}
			
		else
			printf("%.1f\n",sum/2);	
	}
	
	return 0;
}