【BFS】GZOI2011廣州2011選拔賽：理財年代 money 解題報告

【問題描述】

最近通貨膨脹很厲害，CPI跑得比銀行利息要快，要抗通脹，又要避風險，其中一種很好的方式，就是購買銀行發行的理財產品。雖然理財產品的利息比銀行定期要高，而且沒有風險，但是，購買理財產品需要一定的資金門檻，而且還要保證吧錢存入一定時間不能取出來，因此也是有一定的限制的。

小郭很喜歡研究銀行的理財產品，她計劃在2011年拿10萬元進行理財產品的投資，為了簡單方便，她在2011年每次投資理財產品時，都是把這筆資金和之前購買理財產品產生的所有利息投入進去，希望在年底獲取最高的利潤。

【理財產品】

一個理財產品有如下要素：

資金門檻：至少要投入多少資金；

發行時間：該理財產品的購買時間；

投資天數：資金存放的天數，

年利息：該理財產品如果存放一年365天能獲取的利息。

由於郭小姐選擇的所有理財產品的門檻都是10萬以內，因此理財產品就剩下的3個要素。

例如，A1理財產品，發行時間是3月1日，投資天數為30天，年利息為 3.5%，那麼，如果10萬元購買該產品，那麼在30天后，也就是3月30日收市後，她可以獲得的資金為：

`100000*(1+0.035*30/365)=100287.67元 （四捨五入，保留2位小數）

然後，她就可以吧100287.67元這筆資金，購買3月31日或之後發行的任何理財產品。

郭小姐在這一年內不斷把本金和利息一起全額地購買理財產品，希望在2012年到來之前獲得最高的收益。如果購買的兩個理財產品之間有時間間隔，那麼這筆錢就不能產生利潤（銀行活期利息太低，利潤可以忽略）。請問她這年內，能通過購買理財產品，最多獲取多少錢呢？

【輸入格式】

第一行是整數N(1<=N<=15)，代表理財產品的數目

下面N行為3個由空格隔開的字元串 A B C

A代表發行時間，格式為MMDD（兩位月兩位日），例如4月1日則為0401，10月2日則為1002

B (整數)，代表投資天數，範圍是[10,300]

C (最多2位的小數)，代表百分之幾的年利息，範圍是[3,30]

輸入資料保證 發行時間+投資天數不會超過2012年。

【輸出格式】

輸出只有一行，為年底最多可獲得的連本帶利的資金數目，保留2位小數

【輸入樣例】

3

0101 100 4.5

0201 30 5

0402 50 7.8

【例子分析】

例子中的3個理財產品，只能購買1號產品，或者連續購買2號、3號理財產品。

購買1號理財產品的收益為 100000*(1+0.045*100/365)=101232.88

購買2/3號理財產品的收益為：

購買2號產品後總資金： 100000*(1+0.05*30/365)=100410.96

再購買3號產品後總資金： 100410.96*(1+0.078*50/365)=101483.84

因此最高收益為 101483.84

【輸出樣例】

101483.84

【分析】

本題是廣州NOI選拔賽中比較簡單的一道，可以用BFS廣度優先搜索做。由於N很小、而且減枝十分有效，所以隊列會很小。

本題易錯地方有：

1) 日期的轉換和判斷

2) 利息的計算

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int N;
class Money
{
public:
    int Mon;
    int Days;
    int Day1;
    int Day2;
    int Time;
    double Rate;
}M[30];

int days(int b,int c) 
{ 
    int d=0; 
    if(b==1) d=c; 
    if(b==2) d=31+c; 
    if(b==3) d=60+c; 
    if(b==4) d=91+c; 
    if(b==5) d=121+c; 
    if(b==6) d=152+c; 
    if(b==7) d=182+c; 
    if(b==8) d=213+c; 
    if(b==9) d=244+c; 
    if(b==10) d=274+c; 
    if(b==11) d=305+c; 
    if(b==12) d=335+c; 
    return d; 
} 

int cmp(const void *a,const void *b)
{
    class Money *c=(class Money *)a;
    class Money *d=(class Money *)b;
    if(c->Day1!=d->Day1)
        return c->Day1-d->Day1;
    return c->Day2-d->Day2;
}

void init()
{
    scanf("%d\n",&N);
    int tmp1,tmp2;
    char ch1,ch2;
    for (int i=1;i<=N;i++)
    {
        scanf("%c%c",&ch1,&ch2);
        tmp1=(ch1-'0')*10+ch2-'0';
        scanf("%c%c",&ch1,&ch2);
        tmp2=(ch1-'0')*10+ch2-'0';
        M[i].Mon=tmp1;
        M[i].Days=tmp2;
        M[i].Day1=days(tmp1,tmp2);
        scanf("%d %lf\n",&M[i].Time,&M[i].Rate);
        M[i].Day2=M[i].Day1+M[i].Time-1;
    }
    qsort(M+1,N,sizeof(M[0]),cmp);
}

class QUEUE
{
public:
    double money;
    int pos;
    int day;
}Q[100000];

double GetMoney(double ben,int num)
{
    double res=ben;
    double rate=double(1)+M[num].Rate*(double(M[num].Time)/double(365))/(double(100));
    res=res*rate;
    return res;
}

void bfs()
{
    double S=0;
    int head=N;
    int rear=0;
    for (int i=1;i<=N;i++)
    {
        Q[i-1].pos=i;
        Q[i-1].money=GetMoney(double(100000),i);
        Q[i-1].day=M[i].Day2+1;
    }
   
    double tm;
    int td;
    int tp;
    while(rear<head)
    {
        tm=Q[rear].money;
       
        if(tm>S)
            S=tm;
       
        td=Q[rear].day;
        tp=Q[rear].pos;
        for(int i=tp+1;i<=N;i++)
        {
            if(M[i].Day1>=td)
            {
                Q[head].money=GetMoney(tm,i);
                Q[head].pos=i;
                Q[head].day=M[i].Day2+1;
                head++;
            }
        }
        rear++;
    }
    printf("%.2lf\n",S);
}


int main()
{
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    init();
    bfs();
    return 0;
}