地铁间谍, 我感觉前缀和和dp都处理好了, 但是不理解为什么输出都为 0 0
查看原帖
地铁间谍, 我感觉前缀和和dp都处理好了, 但是不理解为什么输出都为 0 0
575850
RemainThrive楼主2022/3/23 10:00
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int N, T;
int m1, m2;
int st[100], ed[100];
bool ri[2010][60], le[2010][60];
int dp[2010][60];
int sum[60];
void init(){
    memset(sum, 0, sizeof(sum));
    memset(ri, 0, sizeof(ri));
    memset(le, 0, sizeof(le));
    memset(dp, 0x3f, sizeof(dp));
}
int main(void){
    int cnt = 0;
    while (~scanf("%d", &N)){
        if (N == 0) break;
        void init();
        cin >> T;
        for (int i = 2; i <= N; i++){
            cin >> sum[i];
            sum[i] += sum[i-1];
        }
        cin >> m1;
        for (int i = 1; i <= m1; i++){
            cin >> st[i];
            for (int j = 1; j <= N; j++){
                ri[st[i]+sum[j]][j] = 1;
                
            }
        }
        cin >> m2;
        for (int i = 1; i <= m2; i++){
            cin >> ed[i];
            for (int j = N; j >= 1; j--){
                le[ed[i]+sum[N]-sum[j]][j] = 1;
            }
        }
        dp[0][1] = 0;
        for (int i = 0; i <= T; i++){
            for (int j = 1; j <= N; j++){
                if (i){
                    dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
                }
                if (ri[i][j]){
                    dp[i+sum[j+1]-sum[j]][j+1] = min(dp[i][j], dp[i+sum[j+1]-sum[j]][j+1]);
                }
                if (le[i][j]){
                    dp[i+sum[j]-sum[j-1]][j-1] = min(dp[i][j], dp[i+sum[j]-sum[j-1]][j-1]);
                }
            }
        }
        printf("Case Number %d: ", ++cnt);
        if (dp[T][N] == INF){
            printf("impossible\n");
        }
        else{
            cout << dp[T][N] << endl;
        }
    }
}
2022/3/23 10:00
加载中...