首页 > ACM题库 > HDU-杭电 > Hdu 1487 Economic phone calls-动态规划[解题报告] C++
2013
12-11

Hdu 1487 Economic phone calls-动态规划[解题报告] C++

Economic phone calls

问题描述 :

The phone you bought a long time ago has a built-in memory that keeps track of all the calls you receive. It logs the date (month and day) and the time (hour and minute) of each call along with the caller’s number. Only a limited number of calls can be logged (memory was still expensive then).

You discover that the limit is almost reached and therefore plan to delete some entries from the log. In choosing the entries to delete you have to consider two restrictions:

1.There are some (important) entries you want to keep.
2.You want to be able to recover the year (which the phone does not log) of each call you keep. The recovery procedure is described below.
Calculate the minimal number of entries that must be kept to satisfy these requirements.

Hint

Recovery of years

Given a list of timestamps (consisting of month, day, hour, and minute) of calls, you find out the year of each call by the following procedure:

1.The last call in the list occurred in the current year.
2.You compare its timestamp t to the timestamp t’ of the previous call. If t’<t, you assume that both calls occurred in the same year. If t’≥t, you assume that the previous call occured the year before.
3.You iterate backwards through the list and reason as in 2. at each step.

Note that this procedure is not correct in general, but you may assume that it is for the input you get, and you have to ensure that it gives the same result for the shortened log.

输入:

The input consists of several test cases. Every test case starts with the number of entries n in the log, where 1≤n≤1000. Each of the next n lines contains an entry.

Every entry has the format mm:dd:HH:MM number ±, describing the month mm, day dd, hour HH, minute MM, and number (having 1-16 digits) of each call, followed by + marking a call you definitively want to keep and by – marking the other calls. The entries come directly from the log of the phone, that is, they are sorted by time of reception of the corresponding call (the last entry is the most recent).

You may assume that the recovery procedure described above yields the correct year of each call.

The last test case is followed by a 0.

输出:

For each test case, output the minimal number of entries that must be kept to satisfy the requirements stated above. In particular, the recovery procedure described above must yield for each remaining entry the same year as derived from the corresponding input.

样例输入:

7
12:31:23:59 0123456789012345 +
07:21:19:00 1337 -
01:01:00:00 0987654321 -
07:21:14:00 1337 -
11:11:11:11 11111111111 +
01:01:00:00 0123456789 +
01:01:00:00 0987654321 -
0

样例输出:

6
Hint

P.S.

Due to an error in the phone’s software no calls have been logged on February 29.

此题的核心就是选择,按时间顺序进行选择的话,可以发现每次选择只和当前选择的集合中时间最晚的电话有关。

所以可以dp。

令f[i][j]为处理了前i个电话,当前选择的电话中最晚的电话为j时,选择的最少电话数。

对于i而言,如果选择i,则有f[i][i]=min{f[i-1][j]},其中1<=j<i,且由j可以判断出i的正确时间。

同时,如果i是今年的电话,则除了上面的转移,还有f[i][i]=min(f[i][i],f[i-1][0]+1)。

如果不选择i,则有f[i][j]=f[i-1][j]。

考虑到可能有前面没有选择的电话,所以这种情况用0表示。

注意边界,如果i是必须选择的,则f[i][0]=INF,否则f[i][0]=f[i-1][0]。

还要注意,最后一个电话才是最近的电话!!!

【代码】

#include  
#include  
#include  
#include  
#include  
using namespace std; 
 
const int N=1003,INF=100000; 
 
struct date 
{ 
    int mon,day,h,min; 
    bool operator >=(const date& y) 
    { 
        if (mon>y.mon) return true; 
        if (mony.day) return true; 
        if (dayy.h) return true; 
        if (h=y.min) return true; 
        else return false; 
    } 
}a[N]; 
 
int f[N][N],y[N]; 
bool v[N]; 
 
int main() 
{ 
    int i,j,n,ty,ans; 
    char ch; 
 
    freopen("in","r",stdin); 
    while (1) 
    { 
        scanf("%d\n",&n); 
        if (n==0) break; 
        if (n<=10) 
        { 
            i=0; 
        } 
        for (i=n;i>=1;i--) 
        { 
            scanf("%d:%d:%d:%d %d %c\n",&a[i].mon,&a[i].day,&a[i].h, 
                  &a[i].min,&j,&ch); 
            if (ch=='+') v[i]=true; 
            else v[i]=false; 
        } 
        y[1]=0; 
        for (i=2;i<=n;i++) 
            if (a[i]>=a[i-1]) y[i]=y[i-1]+1; 
            else y[i]=y[i-1]; 
        f[1][1]=1; 
        if (v[1]) f[1][0]=INF; 
        else f[1][0]=0; 
        for (i=2;i<=n;i++) 
            f[1][i]=INF; 
        for (i=2;i<=n;i++) 
        { 
            for (j=1;j<=n;j++) 
                f[i][j]=INF; 
            if (v[i]) f[i][0]=INF; 
            else f[i][0]=f[i-1][0]; 
            if (v[i]) 
            { 
                if (y[i]==0) f[i][i]=min(f[i][i],f[i-1][0]+1); 
                for (j=1;j=a[j]) ty=y[j]+1; 
                    else ty=y[j]; 
                    if (ty!=y[i]) continue; 
                    f[i][i]=min(f[i][i],f[i-1][j]+1); 
                } 
            } 
            else 
            { 
                for (j=1;j<=n;j++) 
                    f[i][j]=f[i-1][j]; 
                if (y[i]==0) f[i][i]=min(f[i][i],f[i-1][0]+1); 
                for (j=1;j=a[j]) ty=y[j]+1; 
                    else ty=y[j]; 
                    if (ty!=y[i]) continue; 
                    f[i][i]=min(f[i][i],f[i-1][j]+1); 
                } 
            } 
        } 
        ans=INF; 
        for (i=1;i<=n;i++) 
            ans=min(ans,f[n][i]); 
        if (ans>=INF) ans=n; 
        printf("%d\n",ans); 
    } 
} 

  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?