QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#464432 | #6955. Assignment | fsavcxz | WA | 180ms | 5924kb | C++20 | 2.2kb | 2024-07-06 04:54:09 | 2024-07-06 04:54:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
#define pb push_back
#define ll long long
ll a[N],b[N],cost[N][N],dp[N][N][13],tp[N][N][13];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("in", "r", stdin);
int T;
cin >> T;
while(T--){
int n,k;
cin >> n >> k;
for(int i = 1;i <= n;i++)cin >> a[i];
for(int i = 1;i <= n;i++)cin >> b[i];
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
cin >> cost[i][j];
}
}
for(int i = 0;i <= n + 1;i++){
for(int j = 0;j <= n + 1;j++){
for(int t = 0;t <= k;t++){
dp[i][j][t] = (ll)1e12;
tp[i][j][t] = (ll)1e12;
}
}
}
for(int l = 1;l <= n;l++){
if(a[l] == b[l]){
dp[l][l][0] = 0;
}else{
dp[l][l][1] = 0;
dp[l][l][0] = cost[b[l]][1];
}
}
for(int l = n;l >= 1;l--){
tp[l][l - 1][0] = 0;
for(int cur = 0;cur <= k;cur++){
for(int r = l + 1;r <= n;r++){
if(b[l] == b[r]){
tp[l][r][cur] = min(tp[l][r][cur], tp[l][r - 1][cur]);
}else{
if(cur)tp[l][r][cur] = min(tp[l][r][cur], tp[l][r - 1][cur - 1]);
}
for(int i = l;i < r;++i){
for(int x = 0;x <= cur;x++){
tp[l][r][cur] = min(tp[l][r][cur], tp[l][i][x] + tp[i + 1][r][cur - x]);
}
}
}
}
for(int r = l + 1;r <= n;r++){
for(int x = 0;x <= k;x++){
dp[l][r][x] = min(dp[l][r][x], tp[l][r][x] + cost[b[l]][r - l + 1]);
}
for(int i = l;i < r;++i){
for(int x = 0;x <= k;x++){
for(int y = 0;x + y <= k;y++){
dp[l][r][x + y] = min(dp[l][r][x + y], dp[l][i][x] + dp[i + 1][r][y]);
}
}
}
}
}
cout << dp[1][n][0] << ' ';
for(int x = 1;x <= k;x++){
dp[1][n][x] = min(dp[1][n][x], dp[1][n][x - 1]);
cout << dp[1][n][x] << ' ';
}
cout << '\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 180ms
memory: 5924kb
input:
10 100 10 24 56 71 49 70 39 19 23 96 26 85 33 73 84 35 75 58 77 85 40 33 36 75 55 7 28 37 7 100 94 35 64 68 46 77 80 90 28 85 8 9 23 32 45 4 51 47 82 6 49 45 55 28 69 80 7 61 41 83 42 16 25 82 56 26 92 14 66 43 1 2 62 25 84 19 58 35 37 14 61 38 12 27 95 98 100 61 36 75 83 35 19 74 56 87 10 10 6 60 5...
output:
31600238 30666836 29768969 28871102 27981406 27133126 26345152 25557178 24780724 24007882 23235040 37783284 36857811 35985761 35139146 34292531 33491639 32690747 31889855 31107845 30363672 29620314 36658908 35884678 35110448 34336218 33561988 32787758 32013528 31239298 30465068 29690838 28916608 ...
result:
wrong answer 1st lines differ - expected: '27473279 26539877 25650181 248...3001 20960159 20221324 19493165', found: '31600238 30666836 29768969 288...178 24780724 24007882 23235040 '