HDU 1074 - 압축 DP

2420 단어
처음으로 블로그를 썼는데 dp를 처음 이해한 것 같아요. (기억화 검색이라고 썼는데 지금 생각해도 이해하기 어렵지 않아요)
HDU 1074,
제목은 작업 순서를 정하는 것입니다. 이곳의 압축 상태, 0은 하지 않고 1은 했습니다. 그리고 다음 상태를 검색합니다. 광범위한 검색과 유사하지만 비교할 수 있는 가장 좋은 상태입니다. 여기는 기억화 검색과 같이 모든 검색한 상태를 저장합니다. (dp는 특수한 기억화 검색일 수 있습니다?)
다음은 코드를 보십시오
#include <iostream>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

int dp[1<<16];
int arr[1<<16];
int vis[1<<16];
string as[1<<16];
char s[15][100];
int dead[15];
int many[15];
int n;

void solve(){

    queue<int> q;
    q.push(0);
    vis[0]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<n;i++){
            //    
            int xx=(x|(1<<i));
            //      ,     
            if(vis[xx]==0){
                for(int j=0;j<n;j++){
                    if((xx>>j)%2==1){
                        int yy=(~((~xx)|(1<<j)));
                        int jia=dead[j]-arr[yy]-many[j];
                        if(jia>0)
                            jia=0;
                        if(dp[xx]<dp[yy]+jia){
                            dp[xx]=dp[yy]+jia;
                            arr[xx]=arr[yy]+many[j];
                            as[xx]=as[yy]+'
'+(string)s[j]; } else if(dp[xx]==dp[yy]+jia){ arr[xx]=arr[yy]+many[j]; as[xx]=as[yy]+'
'+(string)s[j]; } } } q.push(xx); vis[xx]=1; } else{ continue; } } } } int main() { int t; cin>>t; while(t--){ scanf("%d",&n); memset(arr,0,sizeof(arr)); memset(vis,0,sizeof(vis)); //memset(dp,0,sizeof(dp)); for(int i=0;i<(1<<n);i++){ dp[i]=-999999; } for(int i=0;i<n;i++){ scanf("%s %d %d",s[i],&dead[i],&many[i]); } dp[0]=0; arr[0]=0; solve(); cout<<-dp[(1<<n)-1]<<endl; cout<<as[(1<<n)-1].substr(1,as[(1<<n)-1].size())<<endl; } }

코드를 못생겼고 최적화도 안 됐어요.

좋은 웹페이지 즐겨찾기