UESTC 2016 Summer Training #2 Div.2 A dp、递推、多阶段问题

Source

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121703#problem/A

My Solution

训练的时候刚开始想到的是记忆化搜索， 但无论怎么优化还是TLE 3，没办法，想想递推怎么写

但是转化方程还是有点小问题， WA5

然后后来才想明白

只要 dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + s[i][j];
if(dp[i][j] > 0) dp[i][j] = 0;

这里不要讨论s[i][j]的正负，都是直接加上s[i][j]就好了

然后处理好边界就好了

dp检查的时候应当着重与转移方程啊⊙﹏⊙‖∣

#include 
#include 
#include 
using namespace std;
const int maxn = 500 + 8;
int s[maxn][maxn], r, c, dp[maxn][maxn];

//int pq; //!!!!!!在这些最小值里，找出最大的一个
/*
void dfs(int a, int b, int sum, int maxmin)
{
    if(maxmin < pq) return;
    if(a == r-1 && b == c - 1) {
        pq = max(maxmin, pq);return;
    }

    if(a + 1 < r) dfs(a + 1, b, sum + s[a+1][b], maxmin = min(sum + s[a+1][b], maxmin));
    if(b + 1 < c) dfs(a, b+1, sum + s[a][b+1], maxmin = min(sum + s[a][b+1], maxmin));
}
*/
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL
    int T;
    scanf("%d", &T);
    while(T--){
        //memset(dp, 0x3f3f, sizeof dp);
        scanf("%d%d", &r, &c);
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                scanf("%d", &s[i][j]);
            }
        }
        /*TLE 5
        pq = 10000000;int sumt = 0;
        for(int i = 0; i < c; i++){
            sumt += s[0][i];
            pq = min(pq, sumt);
        }
        for(int j = 1; j < r; j++){ sumt += s[j][c-1]; pq = min(pq, sumt); } dfs(0, 0, s[0][0], 10000000); */ for(int i = r - 1; i >= 0; i--){
            if(i == r - 1) dp[r-1][c-1] = 0;
            else {
                dp[i][c-1] = s[i][c-1] + dp[i+1][c-1];
                if(dp[i][c-1] > 0) dp[i][c-1] = 0;
            }
            for(int j = c - 2; j >= 0; j--){
                if(i != r - 1) {
                    dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + s[i][j];
                    if(dp[i][j] > 0) dp[i][j] = 0;

                }
                else {
                    dp[i][j] = s[i][j] + dp[i][j+1];
                    if(dp[i][j] > 0) dp[i][j] = 0;
                }
            }
        }
        /*

        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){ printf("%d ", dp[i][j]); } printf("n"); } */ if(dp[0][0] > 0)printf("1n");
        else {printf("%dn", -dp[0][0]+1);}
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx