UESTC 2016 Summer Training #2 Div.2 A dp, 점진적 문제
Time Limit:336MS Memory Limit:1572864KB 64bit IO Format:%lld & %llu
Submit
Status
Practice
SPOJ AMR11A
Description
Thanks a lot for helping Harry Potter in finding the Sorcerer's Stone of Immortality in October. Did we not tell you that it was just an online game ? uhhh! now here is the real onsite task for Harry. You are given a magrid S ( a magic grid ) having R rows and C columns. Each cell in this magrid has either a Hungarian horntail dragon that our intrepid hero has to defeat, or a flask of magic potion that his teacher Snape has left for him. A dragon at a cell (i,j) takes away |S[i][j]| strength points from him, and a potion at a cell (i,j) increases Harry's strength by S[i][j]. If his strength drops to 0 or less at any point during his journey, Harry dies, and no magical stone can revive him.
Harry starts from the top-left corner cell (1,1) and the Sorcerer's Stone is in the bottom-right corner cell (R,C). From a cell (i,j), Harry can only move either one cell down or right i.e., to cell (i+1,j) or cell (i,j+1) and he can not move outside the magrid. Harry has used magic before starting his journey to determine which cell contains what, but lacks the basic simple mathematical skill to determine what minimum strength he needs to start with to collect the Sorcerer's Stone. Please help him once again.
Thanks a lot for helping Harry Potter in finding the Sorcerer's Stone of Immortality in October. Did we not tell you that it was just an online game ? uhhh! now here is the real onsite task for Harry. You are given a magrid S ( a magic grid ) having R rows and C columns. Each cell in this magrid has either a Hungarian horntail dragon that our intrepid hero has to defeat, or a flask of magic potion that his teacher Snape has left for him. A dragon at a cell (i,j) takes away |S[i][j]| strength points from him, and a potion at a cell (i,j) increases Harry's strength by S[i][j]. If his strength drops to 0 or less at any point during his journey, Harry dies, and no magical stone can revive him.
Harry starts from the top-left corner cell (1,1) and the Sorcerer's Stone is in the bottom-right corner cell (R,C). From a cell (i,j),
Harry can only move either one cell down or right i.e., to cell (i+1,j) or cell (i,j+1) and he can not move outside the magrid. Harry has used magic before starting his journey to determine which cell contains what, but lacks the basic simple mathematical skill to
determine what minimum strength he needs to start with to collect the Sorcerer's Stone. Please help him once again.
Input (STDIN):
The first line contains the number of test cases T. T cases follow. Each test case consists of R C in the first line followed by the description of the grid
in R lines, each containing C integers. Rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Cells with
S[i][j] < 0 contain dragons, others contain magic potions.
Output (STDOUT):
Output T lines, one for each case containing the minimum strength Harry should start with from the cell (1,1) to have a positive strength through
out his journey to the cell (R,C).
Constraints:
1 ≤ T ≤ 5
2 ≤ R, C ≤ 500
-10^3 ≤ S[i][j] ≤ 10^3
S[1][1] = S[R][C] = 0
Sample Input:
3 2 3 0 1 -3 1 -2 0 2 2 0 1 2 0 3 4 0 -2 -3 1 -1 4 0 -2 1 -2 -3 0
Sample Output:
2 1 2
Explanation:
Case 1 : If Harry starts with strength = 1 at cell (1,1), he cannot maintain a positive strength in any possible path. He needs at least strength = 2 initially.
Case 2 : Note that to start from (1,1) he needs at least strength = 1.
Hint
Added by:
Varun Jalan
Date:
2011-12-15
Time limit:
0.336s
Source limit:
50000B
Memory limit:
1536MB
Cluster:
Cube (Intel G860)
Languages:
All
Resource:
Anil Kishore - ICPC Asia regionals, Amritapuri 2011
Source
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121703#problem/A
My Solution
훈련할 때 처음에 생각나는 것은 기억화 검색인데 아무리 최적화를 해도 TLE 3이고 어쩔 수 없어요. 밀어붙이고 어떻게 쓰는지 생각해 봐요.
하지만 전환 방정식은 작은 문제가 있다.
나중에 깨달았어요.
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("
");
}
*/
if(dp[0][0] > 0)printf("1
");
else {printf("%d
", -dp[0][0]+1);}
}
return 0;
}
Thank you!
------from ProLights
좋은 웹페이지 즐겨찾기
