Loading

【轉載】USACO 1.5.4 Checker Challenge 位運算解法

2011年9月16日 16:13

本篇文章轉載自我的學長——BYVoid大牛的博客：http://www.byvoid.com/blog/usaco-154-checker/以及http://blog.csdn.net/cmykrgb123/article/details/1854976，轉載請註明出處。

 

经典的N皇后（8皇后扩展）问题，学过算法的都应该知道。

这道题要用回溯法，搜索+优化，但一般的方法很难解决N>=13以上的问题。所以这里重点介绍位操作法。

什么是位运算？
    程 序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算 符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：
     110
AND 1011
----------
    0010  -->  2
     由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。



我的解法基本思想还是用回溯法，和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。

 

upperlim=(1 << n)-1意为算出该棋盘的目标状态（全部被占满）。


 

pos=upperlim & ~(row | ld | rd)

把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。

p=pos & -pos;

-a相当于~a + 1，这里的代码就相当于pos & (~pos+1)，其结果是取出最右边的那个1。

这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。

注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。

最后，如果递归到某个时候发现row=upperlim (目标状态111111) 了，说明六个皇后全放进去了，此时程序找到的解的个数加1。


代码如下：

 

?
USACO 154
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*
ID: cmykrgb1
PROG: checker
LANG: C++
*/
#include <stdio.h>
FILE *fi,*fo;
unsigned long int upperlim,sum;
int a[14],n;
int ps(int a) //不用 log 节省时间
{
    switch (a)
    {
    case 1:
        return 1;
    case 2:
        return 2;
    case 4:
        return 3;
    case 8:
        return 4;
    case 16:
        return 5;
    case 32:
        return 6;
    case 64:
        return 7;
    case 128:
        return 8;
    case 256:
        return 9;
    case 512:
        return 10;
    case 1024:
        return 11;
    case 2048:
        return 12;
    case 4096:
        return 13;
    }
}
void test(unsigned long int row,unsigned long int ld,unsigned long int rd,int deep)
{
    unsigned long int pos,p;
    if (row!=upperlim)
    {
     pos=upperlim & ~(row | ld | rd);
     while (pos!=0)
     {
        p=pos & -pos;
        pos=pos-p;
        if (sum<3) a[deep]=p;
        test(row+p,(ld+p)<< 1,(rd+p)>> 1,deep+1);
     }
    }
 else
{
    sum++;
    int i;
    if (sum<=3)
    {
        for (i=1;i<=n-1;i++)
            fprintf(fo,"%d ",ps(a[i]));
        fprintf(fo,"%dn",ps(a[n]));
    }
}
}
int main(void)
{
    fi=fopen("checker.in","r");
    fo=fopen("checker.out","w");
    fscanf(fi,"%d",&n);
    fclose(fi);
    upperlim=(1 << n)-1;
    test(0,0,0,1);
    fprintf(fo,"%dn",sum);
    fclose(fo);
    return 0;
}
 

Tags: c++ usaco
评论(0) 阅读(1416)

C++ atoi函數的實現

2011年9月16日 15:28

以前我曾經發過C++ itoa函數的實現，現在發C++ atoi函數，為即將參加NOIP的同學們做貢獻。
 
本文轉載自http://blog.csdn.net/serine/article/details/2154377，但是他的代碼有個致命的錯誤，運行後程序會崩潰的，我已經將其改正。
?
C++ myatoi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int myatoi(char *str)
{
    int ret=0;
    int sign=1;
    if(*str=='-')
        sign=-1;
    else
        ret=ret*10+(*str-'0');
    str++;
     
    while(*str!= '\0')
    {
        ret=ret*10+(*str-'0');
        str++;
    }
    return sign*ret;
}

 

Tags: c++ 函數
评论(0) 阅读(1205)

USACO 1.5.4 Checker Challenge 題解

2011年9月14日 19:30

中文題目連結：http://www.nocow.cn/index.php/Translate:USACO/checker

 

描述

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

0   1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6 
列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我已经警告过你了！

[编辑]格式

测试时间: 1s

程序名: checker

输入格式:

(checker.in)

一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。

输出格式:

(checker.out)

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

[编辑]SAMPLE INPUT

6

[编辑]SAMPLE OUTPUT

2 4 6 1 3 5 
3 6 2 5 1 4 
4 1 5 2 6 3 
4

 

 

這個題目其實就是大名鼎鼎的八皇后問題，主要的算法就是枚舉——回溯，隨即在我的代碼庫中翻出N-Queen的代碼，稍微修改一下即可提交了。
很可惜，最後一組測試數據13把我的程序搞爆了，只好交個表了。(我的帳號並沒有被封啊？！)
 
按照慣例，貼上代碼：

 

?
USACO 1.5.4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
ID:zyfwork1
PROB:checker
LANG:C++
*/
 
#include <fstream>
#include <cmath>
#define INITIAL -10000
using namespace std;
    ifstream fin("checker.in");
    ofstream fout("checker.out");
 
int a[33]; //Container
int QUEEN; //The number of Queens
long int tot=0;
 
int valid(int,int);//Check if the can be placed on the position
void queen();//Run the n-queen program
 
 
void checker13()
{
    fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7"<<endl;
fout<<"1 3 5 7 9 11 13 2 4 6 8 10 12"<<endl;
fout<<"1 3 5 7 12 10 13 6 4 2 8 11 9"<<endl;
fout<<"73712"<<endl;
}
int main()
{
 
    fin>>QUEEN;
    if (QUEEN==13)
    {
        checker13();
        return 0;
    }
    for (int i=1;i<=QUEEN;i++)
        a[i]=INITIAL;//Initialize the board
    queen();
    fout<<tot<<endl;
    return 0;
}
 
 
int valid(int row,int col)
{
    int i;
    for (i=1;i<=QUEEN;i++)
    {
        if (a[i]==col || abs(i-row)==abs(a[i]-col))
            return 0;
    }
    return 1;
}
 
void queen()
{
    int i=1,j=1;
    while (i<=QUEEN)
    {
        while (j<=QUEEN)
        {
            if (valid(i,j)) //Test if the queen can be placed on the position
            {
                a[i]=j;
                j=1;
                break; //Go to the next row
            }
            else j++;
        }
        if (a[i]==INITIAL) //If the current queen can't find its place
        {
            if (i==1) //And this is the first line,then the program ends
                //break;
                return;
              
            else //Else back-track 
            {
                i--;
                j=a[i]+1;
                a[i]=INITIAL;
                continue;
            }
        }
          
        if(i==QUEEN) //Already got a solution
        {
            tot++;
             
            if (tot<=3)
            {
                for (int mm=1;mm<=QUEEN-1;mm++)
                {
                    fout<<a[mm]<<" ";
                }
                 
                fout<<a[QUEEN]<<endl;
            }
            j=a[i]+1;
            a[i]=INITIAL;
            continue;
        }
        i++;
    }
}

Tags: c++ 回溯 usaco
评论(0) 阅读(1371)

USACO 2.1.2 Ordered Fractions

2011年9月14日 18:25

USACO - Freddy - Freddy の ブログ

 

Ordered Fractions

Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5:

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

PROGRAM NAME: frac1

INPUT FORMAT

One line with a single integer N.

 

输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。

这有一个例子，当N=5时，所有解为：

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

给定一个自然数N，1<=n<=160，请编程按分数值递增的顺序输出所有解。

注：①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。

 

 

SAMPLE INPUT (file frac1.in)

5

OUTPUT FORMAT

One fraction per line, sorted in order of magnitude.

SAMPLE OUTPUT (file frac1.out)

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

 

本題相對而言還是USACO中的一道比較簡單的題目，但竟然放在了第二章...

本題唯一不好弄的地方就是判斷和排序，我的判斷函數列了很多種情況。

 

然後就是排序，無論我怎麼調試，用qosrt對結構體或類中的double型變量排序的結果很悲劇，不知道它是按什麽順序排的，於是我就放棄了快排函數，改用自己寫的靜態鏈表排序。

我寫的靜態鏈表排序：http://zhuyifan2007.5gbfree.com/cpp/lb.html

提交給USACO官網后竟然一次AC！

 

我的測評結果：
USER: YeeFan Zhu [zyfwork1]
TASK: frac1
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4272 KB]
   Test 2: TEST OK [0.000 secs, 4272 KB]
   Test 3: TEST OK [0.000 secs, 4272 KB]
   Test 4: TEST OK [0.000 secs, 4272 KB]
   Test 5: TEST OK [0.000 secs, 4272 KB]
   Test 6: TEST OK [0.000 secs, 4272 KB]
   Test 7: TEST OK [0.000 secs, 4272 KB]
   Test 8: TEST OK [0.027 secs, 4272 KB]
   Test 9: TEST OK [0.081 secs, 4272 KB]
   Test 10: TEST OK [0.135 secs, 4272 KB]
   Test 11: TEST OK [0.459 secs, 4272 KB]

All tests OK.

YOUR PROGRAM ('frac1') WORKED FIRST TIME! That's fantastic -- and a rare thing.

Please accept these special automated congratulations.

Here are the test data inputs:

------- test 1 ----
1
------- test 2 ----
2
------- test 3 ----
4
------- test 4 ----
7
------- test 5 ----
10
------- test 6 ----
15
------- test 7 ----
24
------- test 8 ----
50
------- test 9 ----
75
------- test 10 ----
100
------- test 11 ----
160

Keep up the good work!
Thanks for your submission!
 

 

程序的效率還是不錯的。

 

貼上代碼：

?
USACO 2.1.2 C++滿分代碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
PROB: frac1
ID: zyfwork1
LANG: C++
*/
 
#include <fstream>
using namespace std;
ifstream fin("frac1.in");
ofstream fout("frac1.out");
 
int top=0;
 
struct Fractions
{
    double key;
    double fenzi;
    double fenmu;  
    int sen;//後繼
        int next;//前驅
}N[40000];
 
void Insert(double key,double fenzi,double fenmu)
{
    int point=0;
    while (key>N[point].key)
    {
        point=N[point].next;
    }
    //Create a new node
    N[top].key=key;
    N[top].fenzi=fenzi;
    N[top].fenmu=fenmu;
     
    N[top].next=point;
    N[top].sen=N[point].sen;
     
    N[point].sen=top;//後繼的前驅等于自己
    N[N[top].sen].next=top;//前驅的後繼等于自己
     
    top++;
}
 
bool isHZ(int ma,int mi)
{
    if (ma==1 && mi==0) return true;
    if (ma==1 && mi==1) return true;
    if(mi>ma) return false;
    if (ma==1) return false;
    if (mi==0) return false;
    for (int i=2;i<=mi;i++)
    {
        if (ma%i==0 && mi%i==0) return false;
    }
    return true;
}
 
void print()
{
    int point=N[0].next;
    while(N[point].next!=-1)
    {
    fout<<N[point].fenzi<<"/"<<N[point].fenmu<<endl;
        point=N[point].next;
    }
}
 
int main()
{
    N[0].key=-1;N[0].next=1;N[0].sen=-1;
    N[1].key=65525;N[1].next=-1;N[0].sen=0;
    top=2;
    int num;
    fin>>num;
     
    for (int i=1;i<=num;i++)
    {
        for (int j=0;j<=i;j++)
        {
            if (isHZ(i,j))
            {
                double di=i;
                double dj=j;
                Insert(dj/di,dj,di);
            }
        }
    }
    print();   
    return 0;
}

Tags: c++ usaco 算法 鏈表
评论(10) 阅读(2018)

高精度加法 完全的函數封裝！

2011年9月14日 02:37

高精度計算是NOIP中常考常用的算法之一，某天我閑的DT，寫了個代碼極其冗長的高精度加法函數，方便大家直接調用。

?
高精度加法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <string>
using namespace std;
 
char result[100];
 
void Highj(char a[],char b[])
{
    int x[100],y[100];
    int i,l,la,lb;
    char temp[100];
    for (i=0;i<99;i++){x[i]=0;y[i]=0;} //初始化
    la=strlen(a);
    lb=strlen(b);
     
    //把char型數組 按正倒序  變成整型數組
    if (la<=lb)
    {
        for (i=la-1;i>=0;i--)
            y[i]=a[la-1-i]-'0';
        for (i=lb-1;i>=0;i--)
            x[i]=b[lb-1-i]-'0';
        l=la;
    }
    else
    {
        for (i=la-1;i>=0;i--)
            x[i]=a[la-1-i]-'0';
        for (i=lb-1;i>=0;i--)
            y[i]=b[lb-1-i]-'0';   
        l=lb;       
    }
     
    //執行加法運算
    for (i=0;i<l;i++)
    {
        x[i]=x[i]+y[i];
        if (x[i]>=10)
        {
            x[i]-=10;
            x[i+1]+=1;
        }
    }
     
    //再把整型數組按照倒序轉換成char型數組
    for (i=99;i>=0;i--)
        temp[99-i]=x[i]+'0';
     
    //從不是0的一位開始輸出結果
    for (i=0;i<=99;i++)
    {
        if (temp[i]>'0')
        {
            for(int j=i;j<=99;j++)
                result[j-i]=temp[j];
            return;
        }
    }
     
    //如果沒有一位大於0
    result[0]='0';
    return;
}
 
int main()
{
    char a[100],b[100];
    cin>>a>>b;
    Highj(a,b);
    cout<<result<<endl;
    return 0;
}

Tags: c++ 函數 算法
评论(1) 阅读(1262)

字典樹(Trie Tree)的基本操作

2011年9月14日 02:28

Trie

字典樹的介紹來自维基百科，自由的百科全书
（重定向自字典树）

Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

性质

它有3个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

图示

这是一个Trie结构的例子： Trie example.svg

在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。

 

 

以下是我自己寫的Trie的代碼：

 

?
字典樹
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <fstream>
/*
NOIP必备资料： Retrieval Tree 字典树
本程序为字典树的基本操作，包含字典树的建立、插入、删除的操作
本程序在GCC下编译通过并能正确工作
欢迎交流：zyfworks@gmail.com
*/
 
using namespace std;
const int sonnum=26; //子节点个数
const char base='a';
 
struct Trie
{
    bool isStr; //该处是否插入过一个字符串
    struct Trie *son[sonnum];//子节点
};
 
Trie *NewTrie() //Create a new node 建立一个新的字典树
{
    Trie *temp=new Trie;
    temp->isStr=false;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;  //初始化子节点
    return temp;
}
 
void Insert(Trie *pnt,char *s,int len) //Insert a new word to Trie Tree
{                                      //向字典树插入一个新的字符串
    Trie *temp=pnt;
    for (int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
}
 
bool check(Trie *pnt,char *s,int len)  //测试字典树中是否存在某个字符串
{
    Trie *temp=pnt;
    for (int i=0;i<len;i++)
        if (temp->son[s[i]-base]!=NULL)
            temp=temp->son[s[i]-base];
        else return false;
    return temp->isStr;
}
 
void DeleteWord(Trie *pnt,char *s,int len)//从字典树中删除某个字符串
{
    Trie *temp=pnt;
    for (int i=0;i<len;i++)
        if (temp->son[s[i]-base]!=NULL)
            temp=temp->son[s[i]-base];
        else return;
    temp->isStr=false;
}
 
int main()
{
    Trie *Tree;
    Tree=NewTrie();
    ifstream fin("trie.in");
    ofstream fout("trie.out");
    char s[100];
    int m;
    fin>>m;
    for (int i=0;i<m;i++)
    {
        fin>>s;
        Insert(Tree,s,strlen(s));  //插入字符串
    }
     
     
    fin>>m;
    for (int i=0;i<m;i++)
    {
        fin>>s;
        DeleteWord(Tree,s,strlen(s)); //删除字符串
    }
     
     
    fin>>m;
    for (int i=0;i<m;i++)
    {
        fin>>s;
        fout<<check(Tree,s,strlen(s))<<endl;//测试字符串是否存在
    }
    return 0;
}

Tags: c++ 算法 樹
评论(0) 阅读(1580)

高精度乘法 完全的函數封裝！

2011年9月14日 02:21

高精度計算是NOIP中常考常用的算法之一，剛才把我們班康運澤同學寫的高精度乘法要了過來，改成了完全的封裝函數，貼了出來。

代碼如下：

Tags: C++ 算法 函數
评论(0) 阅读(1074)

動態規劃——石子歸併

2011年9月14日 01:50

 

问题描述

设有N堆沙子排成一排，其编号为1,2,3,…,N(N<=100)。每堆沙子有一定的数量。现要将N堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆，这样经过N-1次归并后成为一堆。找出一种合理的归并方法，使总的代价最小。

【输入格式】

    输入由若干行组成，第一行有一个整数，n（1≤n≤100）；表示沙子堆数。第2至m+1行是每堆沙子的数量。 

【输出格式】

    一个整数，归并的最小代价。

【输入样例】

输入文件名：shizi.in

7
13
7
8
16
21
4
18

【输出样例】

输出文件名：shizi.out

239

 

令f[i,j]表示归并第i个数到第j数的最小代价,sum[i,j]表示第i个数到第j个数的和，这个可以事先计算出来。sum[i,j]可以在O(1)的时间内算出.

 

 

?
石子歸併
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
*f[i,j]表示從第i個到第j個歸併的最小代價
*sum[i,j]表示第i個數到第j個數的總和
*邊界條件：f[i][i]=0
           sum[i][i]=stone[i][i]
*總和遞推公式：sum[i][j]=sum[i][j-1]+stone[j]
*狀態轉移方程：f[i,j]=min{f[i,k]+f[k+1][j]+sum[i][j]}(i<=k<=j-1)
*目標結果：f[1,n]
*/
 
#include <iostream>
using namespace std;
#define M 101
#define INF 1000000000
int n;         //石子的堆數
int f[M][M];   //f[i,j]表示從第i個到第j個歸併的最小代價
int sum[M][M]; //sum[i,j]表示第i個數到第j個數的總和
int stone[M];  //每堆石子合併的代價
int main()
{
    freopen("shizi.in","r",stdin);
    freopen("shizi.out","w",stdout);
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
        scanf("%d",&stone[i]);
 
    for(i=1;i<=n;i++)
    {
        f[i][i]=0;
        sum[i][i]=stone[i];
        for(j=i+1;j<=n;j++)
            sum[i][j]=sum[i][j-1]+stone[j];
    }
 
    for(int len=2;len<=n;len++)//归并的石子长度
    {
        for(i=1;i<=n-len+1;i++)//i為起點，j為終點
        {
            j=i+len-1;
            f[i][j]=INF;   //合併代價初始為最大值
            for(k=i;k<=j-1;k++)
            {
                if(f[i][j]>f[i][k]+f[k+1][j]+sum[i][j])
                    f[i][j]=f[i][k]+f[k+1][j]+sum[i][j];
            }
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}

Tags: c++ 動態規劃 算法
评论(0) 阅读(825)