poj 2586

1870 ワード

タイトルリンク:http://poj.org/problem?id=2586
この問題は依然として貪欲なアルゴリズムだ.問題の意味がちょっと分かりにくいです.の利益と損失を出して、それから5ヶ月連続(全部で8個・・・1-5-2-6 3-7・・・8-12)が必ず損失であることを知っていて、最後に利益が得られるかどうか、最大可能性はいくらですか.
考え方:私の考えは1-5月の毎月の利益や損失の状況を求めて、簡単な法則を探してこの5ヶ月を6-10,1,2月に11,12に平行移動すればいいことを発見します.前の5ヶ月の详しい情况を求めて私はすでに始まって意外にもdfsのような方法でしたいと思っています・・・前のテーマの中で2つの问题を练习したのが招いたのではないでしょうか・・・まず5ヶ月をすべて利益に置いて、更に1つ1つ最后の数を交换して、この5ヶ月が全部で赤字になったことを知っています.
あとでよく考えてみると、簡単な算数で前の5ヶ月の状況を求めることができます.そこでまた書きました.の
ここにacコードを添付します.
#include<stdio.h>
#include<string.h>
int s,d;
int flag=0;
int a[15],p[5];
int sum()
{
	int i,q=0;
	for(i=0;i<5;i++)
	{
		q+=a[i];
	}
	return q;
}
void dfs(int depth)
{
	int i;
	if(flag) return;
	if(depth==5)
	{
		if(sum()<0)
		flag=1;
		return;
	}
	for(i=0;i<2;i++)
	{
		a[depth]=p[i];
		dfs(depth+1);
		if(flag) break;
	}
}
int main ()
{
	while (scanf("%d%d",&s,&d)==2)
	{
		flag=0;
		p[0]=s;
		p[1]=-d;
		dfs(0);
		int temp=0;
		/*for(int i=0;i<5;i++)
		printf("%d ",a[i]);*/
		for(int i=5;i<12;i++)
			a[i]=a[i-5];
		for(int i=0;i<12;i++)
			temp+=a[i];
		if(temp>0)
		printf("%d
",temp); else printf("Deficit
"); } return 0; }
acコード2:
#include<stdio.h>
int a[15];
int main ()
{
	int s,d;
	while (scanf("%d%d",&s,&d)==2)
	{
		int sum=0;
		int i,j;
		for(i=5;i>=0;i--)       //     i>=0      i>0        i=1   sum>0     i>0     sum  >0 
		{                      //  i>=0          i=1 sum>0,i=0 sum<0 break 
			sum=i*s-(5-i)*d;
			if(sum<0)break;
		}
		for(j=0;j<i;j++)
			a[j]=s;
		for(j=i;j<5;j++)
			a[j]=-d;
		for(i=5;i<12;i++)
		{
			a[i]=a[i-5];
			sum+=a[i];
		}
		if(sum>0)
		printf("%d
",sum); else printf("Deficit
"); } return 0; }