F.A.Qs Home ProblemSet Status Ranklist 1 Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,鸣谢Claris主持!欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 1592 >> 有望加强数据@管理员
Alextokc @ 2017-05-09 02:52:06
[ Quote ] [ Edit ] [ Delete ] 1#
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

typedef long long int64;
const int oo = 0x3f3f3f3f;
const int NUM = 2005;
int a[NUM], b[NUM], c[NUM];
int dp[NUM][NUM];

int main() {
ios::sync_with_stdio(false);
//dp i, j = 前i个位置非严格单调并且最后一个数字为Bj
//dp i, j = min{dp i - 1, k} + abs(ai - bj) | k = 1..j
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) b[i] = a[i];//非严格递增
sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; ++i) c[i] = b[i];//非严格递减
reverse(c + 1, c + 1 + n);
int x , i, j;
for (i = 1; i <= n; ++i) {
x = oo;
for (j = 1; j <= n; ++j) {
x = min(x, dp[i - 1][j]);
dp[i][j] = x + abs(a[i] - b[j]);
}
}
int ansa = *min_element(dp[n] + 1, dp[n] + n + 1);
cout << ansa << endl;
return 0;
}
不难看出,以上代码,并没有包含非严格递减的情况...
建议多加几组数据,卡掉类似于这样的程序。
Alextokc @ 2017-05-09 02:53:38
[ Quote ] [ Edit ] [ Delete ] 2#
以上代码是错误的,因为少考虑了50%的情况,然而目前确实AC的,
请尽量加强数据,谢谢.
Alextokc @ 2017-05-09 02:58:28
[ Quote ] [ Edit ] [ Delete ] 3#
我也很好奇有些人0ms是怎么做到的...
我的程序不算慢也用了92ms,
难道是因为数据比较弱,
在知道数据的情况下,
打几个小表就搞定了?。。
Alextokc @ 2017-05-11 16:26:37
[ Quote ] [ Edit ] [ Delete ] 4#
@管理员
Alextokc @ 2017-05-11 16:47:42
[ Quote ] [ Edit ] [ Delete ] 5#
@lavendir
lavendir @ 2017-05-17 11:23:05
[ Quote ] [ Edit ] [ Delete ] 6#
请做好相关数据,直接邮件发给我们。谢谢。
Alextokc @ 2017-11-07 08:17:15
[ Quote ] [ Edit ] [ Delete ] 7#
时隔多年,数据造好了。
@lavendir
Alextokc @ 2017-11-07 08:19:08
[ Quote ] [ Edit ] [ Delete ] 8#
已将数据发送到您的邮箱。
@lavendir
lavendir @ 2017-11-07 10:41:03
[ Quote ] [ Edit ] [ Delete ] 9#
已加入,谢谢。
[Top] [Previous Page] [Next Page]

HOME Back