题目描述
「人类不会主动思考。」 曾几何时，天上的神只有一位，然而这话并非出自她口。 那么，这个判定，又是什么样的权威做出的呢？ 「『世界是什么时候开始变成这个样子的？几天前？几个月前？还是很多年以前？抑或原本就是如此，不曾改变？』若没有体验过物是人非，没有人会主动思考这样的问题，人类永远是只记得瞬间的孩子。早上起来第一眼看到什么样的世界，就会本能地认为之前数千年的时光都是这样过来的。只要忍耐或是麻木得足够长，足够久，再特别的记忆也会变成单纯的、无法体验的理论。」 然而，依然有人记得，这段话，并非与世界的历史同源。 「所以呢？思考这样的问题，又有什么样的用处呢？」
一位有着「绯色瞳孔」的舞者。 曾以「神赐之眼」与「治愈之舞」而闻名的舞者。 她想要融入人群。 她是一名舞者。 她会在人群中表演，从而融入群众。 假设人群是一个矩阵，总共有N行M列的人，而她在第一行前面。由于出题人也不知道的原因，她会一行一行地渐渐融入人群。 对于某个第i行第j列的人，只有在此人所要花表演时间tij，他才能接受舞者。同时，若一行的某一个人接受了舞者，那么同一行所有人都会接受舞者。 但是每个人有一个审美观aij，也就是说舞者的舞技只有大于等于aij，那个人才会欣赏她的表演。 假设，舞者的舞技初始为X，她可以在第一行选某一个人表演，再在第二行选一个人……以此类推，一直到行。 对于每次选的人(i,j)（满足aij不小于X），花tij的时间来表演。然后由于某种特殊的原因，表演完她的舞技会更新为cij。 她想知道当她完全融入这个人群后（即每行都选了一个人），她所需最少的时间是多少？ 若舞者无法融入人群，输出-1。
输入
第一行三个数，分别是N,M,X。 接下来要输入三个矩阵，输入格式都是 输入N行 每行M个数。 第一个矩阵，代表tij。 第二个矩阵，代表aij。 第三个矩阵，代表cij。
输出
一行，表示她所需要的最少时间。
样例输入 Copy
2 3 17 7 3 8 9 5 3 12 22 25 12 11 23 15 17 19 11 21 15
样例输出 Copy
12
提示
代码：
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define ll long long
#define inf 0x3f3f3f3f
#define pii pair<int, int>
const int mod
=1e9+7;
const int N
=510;
using namespace std
;
int n
,m
,x
;
int t
[N
][N
],c
[N
][N
],a
[N
][N
],dp
[N
][N
];
int main()
{
memset(dp
,inf
,sizeof(dp
));
cin
>>n
>>m
>>x
;
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
cin
>>t
[i
][j
];
}
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
cin
>>a
[i
][j
];
}
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
cin
>>c
[i
][j
];
}
}
for(int i
=1;i
<=m
;i
++)
{
if(x
>=a
[1][i
]) dp
[1][i
]=t
[1][i
];
}
for(int i
=2;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
for(int k
=1;k
<=m
;k
++)
{
if(dp
[i
-1][k
]==inf
) continue;
if(c
[i
-1][k
]>=a
[i
][j
])
{
dp
[i
][j
]=min(dp
[i
][j
],dp
[i
-1][k
]+t
[i
][j
]);
}
}
}
}
int ans
=inf
;
for(int i
=1;i
<=m
;i
++)
{
ans
=min(ans
,dp
[n
][i
]);
}
if(ans
==inf
) cout
<<"-1";
else cout
<<ans
;
}
