HDU 1422 월드컵 재시작 -- (최장자 시퀀스 모델, bug)
분석: 이 문제는 최장자 서열과 차이가 많지 않다. dp[i]는 i번째 도시를 갈 때 가장 많이 지나간 도시의 수량을 나타낸다. 만약에 i번째 도시의 비용이 충분하다면 dp[i]=dp[i-1]+1이고 복잡도는 O(n)이다.
이 문제는 주로 다음과 같다.TLE.왜냐하면 입력과 출력용cin이고,cout를 표준 입력과 출력으로 바꾸면 돼요.
2.WA.이전에 지나간 도시에서 다 쓰지 못한 비용은 나중에 쓸 수 있는데 이것은 tmp로 보존해야 한다.도시 서열은 순환적이다. 즉, i, i+1,...n-1,0,1,2...이런 순서로 가도 되기 때문에 한 번 순환해서 코드를 보면 알 수 있다.프로그램의 추진 순서가 맞지 않습니다. 앞에서 바뀐 변수는 뒤에 변수가 참여하는 조건 판단 결과에 영향을 줄 수 있습니다. 상세한 것은 코드를 보십시오.
코드:
#include
#include
//#include
using namespace std;
int n;
int dp[100007],mx;
int a[100007],b[100007];
int main()
{
while(scanf("%d",&n)!=EOF){
mx=0;
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i=b[0]){
dp[0]=1;
tmp=a[0]-b[0];
}
for(int i=1;i<2*n;i++){
if(i>=n&&a[i%n]+tmp=b[i%n]){
dp[i%n]=dp[(i-1)%n]+1;
tmp=a[i%n]+tmp-b[i%n];
}
else tmp=0;
mx=mx>dp[i%n]?mx:dp[i%n];//cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.