文章

7

粉丝

387

获赞

7

访问

64.7k

头像
本题数据疑似有误,具体说明在题解中(另附dp/图论两种解法)
P1173 清华大学上机题
发布于2021年1月12日 18:22
阅读数 9.1k

疑似是造的数据未考虑到会爆精度的问题,测试的样例输出超过了int精度,这导致以下代码会被判为AC

#include <cstdio>
#include <climits>
typedef long long ll;
const int maxn = 510;
const int INF = 0x7fffffff;
int dist[maxn], cost[maxn];//第i个站的总里程、最少花费
int l1, l2, l3, c1, c2, c3;
 
int Price(int L) {//L距离的票多少钱
    if(L<=l1) return c1;
    else if(L<=l2) return c2;
    else return c3;
}
int n, from, to;
int main() {
    
    while(scanf("%d%d%d",&l1,&l2,&l3)!=EOF) {
        scanf("%d%d%d",&c1,&c2,&c3);
        dist[1]=0;//始发站里程为0
        scanf("%d%d", &from, &to);
        scanf("%d", &n);
        for(int i=2; i<=n; i++) scanf("%d", &dist[i]);
        cost[from]=0;//出发之前,没花一毛钱
        for(int i=from+1; i<=to; i++) {//前进!!!
            cost[i]= INF;//先假设到i站需要花无数的钱
            for(int j=from; j<i; j++) {//到i站的票可能是从j站买的
                int L=dist[i]-dist[j];//j站到i站的距离
                if(L<=l3&&cost[j]+Price(L)<cost[i])
       ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发