동적 계획 --- - PatMouse 의 속도 (HDU 1160)

HDU 1160 —— FatMouse’s Speed
n 마리 의 쥐 를 정 하고 모든 쥐 는 체중 과 속 도 를 가 집 니 다. 쥐 의 가장 긴 서열 을 구하 여 체중 을 엄 격 히 증가 시 키 고 속 도 를 엄 격 히 감소 시 킵 니 다.이 시퀀스 의 길 이 를 알려 주 고 이 시퀀스 의 모든 쥐 가 입력 한 번 호 를 출력 합 니 다.
문제 풀이 사고: 먼저 모든 쥐 에 게 순 서 를 매 깁 니 다. 첫 번 째 키 워드 는 체중 이 작 을 때 부터 크 고 두 번 째 키 워드 는 속도 가 크 고 작 습 니 다.그리고 이 서열 중의 가장 길 고 엄격 한 서브 서열 을 요구한다.
dp [i] i 마리 쥐 를 마지막 으로 하 는 최 장 합 법 적 인 서열 의 길 이 를 기록 하면 상태 전이 방정식 dp [i] = max {dp [j] + 1}, 0 < = j
마지막 으로 출력 할 때 스 택 으로 출력 합 니 다.
다음은 코드:
#include
#include 
#include 
using namespace std;
struct zc
{
    int w;
    int s;
    int n;
}m[1005];

int dp[1005];

bool comp(const zc &a,const zc&b)
{
    if(a.w!=b.w)
        return a.wb.s;
}
int max(int a,int b)
{
	if(a>b)
		return a;
	else 
		return b;
}

int main()
{
	    int i,j,k;
    for(i=0;i<1005;i++)
        dp[i]=1;

    for(i=1;cin>>m[i].w>>m[i].s;i++)
        m[i].n=i;
    sort(m+1,m+i,comp);

    int maxd=1;
    for(j=2;j m[j].s)
            {
                dp[j] = max(dp[k]+1, dp[j]); 
                if(dp[j] > dp[maxd])
                    maxd = j;
            }
    cout<mm;
    mm.push_back(maxd);                   
    for(j=maxd-1;j>=1;j--)
        if(dp[maxd]==dp[j]+1)
        {
            mm.push_back(j);
            maxd=j;
        }
    for(j=dp[temp]-1;j>=0;j--)
        cout<

좋은 웹페이지 즐겨찾기