11405: 【原1405】畅畅的玩具

题目

题目描述

author: Drei 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1405

题目描述

畅畅有一套玩具小火车，一天他想拼出一段铁轨让他的小火车能走的尽可能长。（一段铁轨由2个相同长度的轨道组成）

畅畅有N（1<=N<=500）根塑料棒，每个塑料棒长为Si，畅畅要从这些塑料棒中挑出一些首尾相连做出两段相同长度的轨道组成铁轨。

输入格式

输入第一行一个正整数N（1<=N<=500）

输入第二行有N个数分别代表Si，数据保证所有Si之和<=2000。

输出格式

输出一个数，表示能组成铁轨的最大长度，如果不能组成两段相同长度的轨道则输出“Impossible”（不包括引号）

Sample Input

5 
1 3 4 5 2

Sample Output

7

解释

样例解释：

左侧轨道：3 + 4 = 7

右侧轨道：5 + 2 = 7

40%的数据N<=100；60%的数据N<=200;

WashSwang's solution

#include <iostream>
#include <cstring>
using namespace std;
int s,n;
int t[501][4001];//前i根棒子中 可以组成的两条长度差为j的轨道中较大的那条的长度
int main() {
    cin>>n;
    memset(t,-1,sizeof(t));
    t[0][0]=0;
    for (int i=1;i<=n;++i)
    {
        cin>>s;
        for (int j=0;j<=2000;++j){
            t[i][j]=t[i-1][j];//不加这根塑料棒
            if (j>=s&&t[i-1][j-s]!=-1&&t[i-1][j-s]+s>t[i][j]) t[i][j]=t[i-1][j-s]+s;//加在较长的那条上 差值变大 较长的长度变大
            if (t[i-1][j+s]>t[i][j]) t[i][j]=t[i-1][j+s];//加在较短的那条上 但并未超过较长的那条 差变小 较长的长度不变
            if (s>=j&&t[i-1][s-j]!=-1&&t[i-1][s-j]+j>t[i][j]) t[i][j]=t[i-1][s-j]+j;//加在较短的那条上 超过了原来较长的那条 长度变大
        }
    }
    if (!t[n][0]) cout<<"Impossible";
    else cout<<t[n][0];
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#include <algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MAX_N 505
#define MAX_S 2010
using namespace std;
int n, sum;
int a[MAX_N];
int f[MAX_N][MAX_S];// f_ij: max height when diff is j with 1~i toothpicks
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
int main() {
    n = read();
    for (register int i = 1; i <= n; ++i) a[i] = read();
    for (register int i = 1; i <= n; ++i) {
        sum += a[i];
        memcpy(f[i], f[i - 1], sizeof(f[0]));
        for (register int j = 0; j <= sum; ++j) {
            // height will at least be j when the diff is j
            if (f[i - 1][j] < j) continue;
            // add i-th toothpick to the longer side
            int diff = j + a[i];
            f[i][diff] = max(f[i][diff], f[i - 1][j] + a[i]);
            // ... shorter side
            diff = abs(j - a[i]);
            f[i][diff] = max(f[i][diff], f[i - 1][j] + a[i]);
        }
    }
    if (f[n][0]) printf("%d\n", f[n][0] >> 1);
    else printf("Impossible");
    return 0;
}