hdu4570Multi-bit Trie (区间DP) - c++编程基础

TOP

hdu4570Multi-bit Trie (区间DP)

2015-07-20 18:06:17 来源: 作者: 【大中小】浏览:3次

Problem Description 　　IP lookup is one of the key functions of routers for packets forwarding and classifying. Generally, IP lookup can be simplified as a Longest Prefix Matching (LPM) problem. That's to find the longest prefix in the Forwarding Information Base (FIB) that matches the input packet's destination address, and then output the corresponding Next Hop information.

　　Trie-based solution is the mZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Qgd2lsZGx5IHVzZWQgb25lIHRvIHNvbHZlIExQTS4gQXMgc2hvd24gaW4gRmlnLjEoYiksIGFuIHVuaS1iaXQgdHJpZSBpcyBqdXN0IGEgYmluYXJ5IHRyZWUuIFByb2Nlc3NpbmcgTFBNIG9uIGl0IG5lZWRzIG9ubHkgdHJhdmVyc2luZyBpdCBmcm9tIHRoZSByb290IHRvIHNvbWUgbGVhZiwgYWNjb3JkaW5nIHRvIHRoZSBpbnB1dCBwYWNrZXQ="s destination address. The longest prefix along this traversing path is the matched one. In order to reduce the memory accesses for one lookup, we can compress some consecutively levels of the Uni-bit Trie into one level, transforming the Uni-bit Trie into a Multi-bit Trie.
　　For example, suppose the strides array is {3, 2, 1, 1}, then we can transform the Uni-bit Trie shown in Fig.1(b) into a Multi-bit Trie as shown in Fig.1(c). During the transforming process, some prefixes must be expanded. Such as 11(P2), since the first stride is 3, it should be expanded to 110(P2) and 111(P2). But 110(P5) is already exist in the FIB, so we only store the longer one 110(P5).
　　Multi-bit Trie can obviously reduce the tree level, but the problem is how to build a Multi-bit Trie with the minimal memory consumption (the number of memory units). As shown in Fig.1, the Uni-bit Trie has 23 nodes and consumes 46 memory units in total, while the Multi-bit Trie has 12 nodes and consumes 38 memory units in total.
Input 　　The first line is an integer T, which is the number of testing cases.
　　The first line of each case contains one integer L, which means the number of levels in the Uni-bit Trie.
　　Following L lines indicate the nodes in each level of the Uni-bit Trie.
　　Since only 64 bits of an IPv6 address is used for forwarding, a Uni-bit Trie has maximal 64 levels. Moreover, we suppose that the stride for each level of a Multi-bit Trie must be less than or equal to 20.
Output 　　Output the minimal possible memory units consumed by the corresponding Multi-bit Trie.
Sample Input

Sample Output

Source 2013 ACM-ICPC长沙赛区全国邀请赛――题目重现题意：一个长度为n的数列，将其分成若干段（每一段的长度要<=20），要求∑ai*(2^bi)最小，其中ai是每一段数列的第一项，bi是每一段的长度, bi<=20。

#include
  
   
__int64 min(__int64 a,__int64 b)
{
    return a>b?b:a;
}
int main()
{
    int n,t;
    __int64 dp[100][100],ans[100];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%I64d",&ans[i]);

        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        dp[i][j]=999999999;//注意初始化
        for(int len=0;len


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 1159 Palindrome DP	下一篇：HDU 2159 FATE(完全背包+二维费用..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: