poj 1205 Water Treatment Plants-DP+ 고정밀

제목이 너무 헷갈려서...
한 라인에'N개의 도시가 있는데 오수 처리 시스템에 연결되어 있고 각 도시는 세 가지 선택이 있다.
1. 자신의 오수를 강에 배출하기 V
2. 자신의 오수를 오른쪽으로 보낸다>
3. 자신의 오수를 왼쪽으로 보낸다<
적어도 한 도시의 배수가 있어야 한다.N개 도시, 방안의 종류를 요구합니다.
맨 왼쪽에는 V,>
명령어 dp[i][0]: V
dp[i][1]:>
dp[i][2]:<
dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
dp[i][2]=dp[i-1][0]+dp[i-1][2]//처음에는 항상 좋았지만 도시 배수 문제가 없는지 모르겠지만 이 방정식은 ><의 상황이 발생하지 않도록 보증한다.
그러나 이 세 방정식은 한 줄이 모두 >>>>>>>인 상황이 발생하지 않을 것을 보장할 수 없기 때문에 마지막 것을 계산할 때 dp[n][0]+dp[n][2]만 계산할 수 있다.
dp[i][0]dp[i][1]가 항상 같기 때문에 상태 이동 방정식을 적게 열거할 수 있음
dp[i][0]=2*dp[i-1][0]+dp[i-1][1]
dp[i][1]=dp[i-1][0]+dp[i-1][1]
즉 dp[i]=3*dp[i-1]-dp[i-2]
여기까지 전체 상태 이동 방정식이 열거되었다.
dp의 값이 클 수 있기 때문에 자바에 있는 BigInteger를 사용해야 합니다. 이것은 제가 처음으로 다른 자바 코드를 보면서 배우면서 두드리는 것입니다. 기념해 주세요~~~~

import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;
public class Main 
{
    public static void main(String[] args) 
    {
        Scanner cin=new Scanner (System.in);
        BigInteger dp[]=new BigInteger[105];
        dp[1]=BigInteger.valueOf(1);
        dp[2]=BigInteger.valueOf(3);
        for(int i=3;i<=100;i++)
            dp[i]=dp[i-1].multiply(new BigInteger("3")).subtract(dp[i-2]);
        while(cin.hasNext())
        {
            int id = cin.nextInt();
            System.out.println(dp[id]);
        }
        System.exit(0);
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

제목이 너무 헷갈려서... 한 라인에'N개의 도시가 있는데 오수 처리 시스템에 연결되어 있고 각 도시는 세 가지 선택이 있다. 1. 자신의 오수를 강에 배출하기 V 2. 자신의 오수를 오른쪽으로 보낸다> 3. 자신의...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

poj 1205 Water Treatment Plants-DP+ 고정밀

좋은 웹페이지 즐겨찾기