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コードを添付します.
この問題は依然として貪欲なアルゴリズムだ.問題の意味がちょっと分かりにくいです.の利益と損失を出して、それから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;
}