Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

小心!这个数据弱!这里ac!zoj上wa!

Posted by Alextokc at 2017-04-13 18:19:47 on Problem 1651
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
using namespace std;

typedef long long int64;
const int oo = 0x3f3f3f3f;
const int NUM = 105;
int cards[NUM], dp[NUM][NUM];

//dp [i][j] = min (dp [i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j])
//最后一个取第k个数

int main() {
    int n;
    cin >> n;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = 0;
        dp[i][i + 1] = 0;
    }
    for (int i = 1; i <= n; ++i) cin >> cards[i];
    for (int i = n; i >= 1; --i) {
        for (int j = i; j <= n; ++j) {
            for (int k = i; k <= j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cards[i] * cards[k] * cards[j]);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}
//上面那个程序,poj上果断ac!
//zoj上wa!scu也是。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator