몇 줄의 흑서의 간단한 DP 문제

11294 단어 동적 기획
이 몇 개의 고전적인 문제는 본래 이 요리로 더 이상 수다를 떨어서는 안 되는데, 어쩔 수 없이 손이 근질근질하여 늘 코드를 붙이려고 한다~
POJ1141 괄호 일치
dp[i][j]는 i에서 j까지 괄호를 최소한 추가해야 할 괄호와 일치하게 하는 것을 나타낸다.
dp[i][i]=1;
dp[i][j]=min(dp[i][k],[k+1][j]);
s[i]=='(', s[j]==')'또는 s[i]=='[', s[j]==']'시 dp[i][j]=min(dp[i][j], dp[i+1][j-1]);
각 dp[i][i]가 추가한 부분이 무엇인지 기록하고 추가된 위치가 앞쪽인지 뒤쪽인지를 기록한다. dp의 과정에서 dp의 경로를 기록하고 dp의 뒤쪽 경로를 따라 풀 수 있다.
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int NN=250;

int n,dp[NN][NN],r[NN][NN];
char s[NN],ad[NN];

void dfs(int i,int j)
{
    if (i>j) return;
    if (i==j)
    {
        if (r[i][i]==-1) putchar(s[i]),putchar(ad[i]);
        else             putchar(ad[i]),putchar(s[i]);
        return;
    }

    if (r[i][j]==0)  { putchar(s[i]); dfs(i+1,j-1); putchar(s[j]); }
    else             { dfs(i,r[i][j]); dfs(r[i][j]+1,j); }
}

int main()
{
    int l,i,j,k,tmp1,tmp2;

    s[0]='0';
    gets(s+1);
    n=strlen(s)-1;
    memset(dp,0,sizeof(dp));
    for (i=1; i<=n; i++)
    {
        dp[i][i]=1;
        if (s[i]=='(') { ad[i]=')'; r[i][i]=-1; }
        if (s[i]=='[') { ad[i]=']'; r[i][i]=-1; }
        if (s[i]==')') { ad[i]='('; r[i][i]=-2; }
        if (s[i]==']') { ad[i]='['; r[i][i]=-2; }
    }
    for (l=1; l<n; l++)
      for (i=1; i<=n-l; i++)
      {
          j=i+l;
          tmp1=n+1;
          for (k=i; k<j; k++)
              if (dp[i][k]+dp[k+1][j]<tmp1)
              {
                  tmp1=dp[i][k]+dp[k+1][j];
                  tmp2=k;
              }
          if ((s[i]=='(' && s[j]==')' || s[i]=='[' && s[j]==']') && dp[i+1][j-1]<tmp1)//      ，WA   
          {
              tmp1=dp[i+1][j-1];
              tmp2=0;
          }
          dp[i][j]=tmp1; r[i][j]=tmp2;
      }

    dfs(1,n);
    printf("
");
    return 0;
}

POJ2288 상태 압축 입문, 해석하지 않는 것은 이 문제가 고전적이지 않고 좋지 않다는 것을 대표하지 않는다. 단지 너무 고전적인 상태 압축이다
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;

int n,m;
LL dp[2][1<<12];

inline bool ok(int x,int y)
{
    int i,j,k;
    for (k=1; k<=m; k++)
    {
        i=x&1; j=y&1;
        x>>=1; y>>=1;
        if (i && j) return false;
        if (!i && !j)
        {
            if (k<m && !(x&1) && !(y&1))
            {
                x>>=1;
                y>>=1;
                k++;
            }
            else return false;
        }
    }
    return true;
}

int main()
{
    int i,j,t,c,lim;

    while (scanf("%d%d",&n,&m),n|m)
    {
        if ((n&1) && (m&1)) { printf("0
"); continue; }
        lim=(1<<m)-1;
        memset(dp[0],0,sizeof(dp[0]));
        dp[0][0]=1;
        for (t=1; t<=n; t++)
        {
            c=t&1;
            memset(dp[c],0,sizeof(dp[c]));
            dp[c][0]=dp[c^1][lim];
            for (i=0; i<lim; i++) if (dp[c^1][i])
              for (j=0; j<=lim; j++) if (ok(i,j))
                  dp[c][j]+=dp[c^1][i];
        }
        printf("%I64d
",dp[c][0]);
    }
    return 0;
}

POJ1112 역도에 대한 연통분량 염색, 두 조로 구성된 가방, 사실 생각지도 못했어요.
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int NN=110;

int n,bn,flag,mp[NN][NN],color[NN],belong[NN],cnt[NN][2];
int ans[NN][NN],id[NN][NN],dp[NN][NN];

void dfs(int u,int c)
{
    color[u]=c;
    belong[u]=bn;
    cnt[bn][c]++;
    for (int i=1; i<=n; i++)
    {
        if (!mp[u][i]) continue;
        if (color[i]==-1) dfs(i,c^1);
        else if (color[i]==c) { flag=0; return; }
    }
}

void get_ans(int i,int k)
{   if (i==0) return;
    ans[i][id[i][k]]=1;
    ans[i][id[i][k]^1]=0;
    get_ans(i-1,k-cnt[i][id[i][k]]);
}

int main()
{
    int i,j,k;

    scanf("%d",&n);
    memset(mp,1,sizeof(mp));

    for (i=1; i<=n; i++)
    {
        mp[i][i]=0;
        while (scanf("%d",&j),j)
            mp[i][j]=0;
    }

    for (i=1; i<=n; i++)
      for (j=1; j<=n; j++) if (mp[i][j])
         mp[j][i]=1;

    bn=0; flag=1;
    memset(color,-1,sizeof(color));
    memset(cnt,0,sizeof(cnt));

    for (i=1; i<=n && flag; i++) if (color[i]==-1) bn++,dfs(i,0);

    if (!flag) { puts("No solution"); return 0; }

    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for (i=1; i<=bn; i++)
      for (j=0; j<=1; j++)
      {
          for (k=(n+1)/2; k>=cnt[i][j]; k--) if (dp[i-1][k-cnt[i][j]])
          {
              dp[i][k]=1;
              id[i][k]=j;
          }
      }
    for (k=(n+1)/2; k; k--) if (dp[bn][k]) break;

    get_ans(bn,k);

    printf("%d",k);
    for (i=1; i<=n; i++) if (ans[belong[i]][color[i]]) printf(" %d",i);
    printf("
%d",n-k);
    for (i=1; i<=n; i++) if (!ans[belong[i]][color[i]]) printf(" %d",i);
    printf("
");

    return 0;
}

POJ1848 트리 DP
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int NN=110;
const int INF=16843009;

int n,ans=0,flag=0;
int  dp[NN][3];
bool vis[NN]={0};
vector<int> adj[NN];

void dfs(int u)
{
    int tmp,i;
    int cnt0=0;
    int cnt1=INF;
    int cnt2=INF;
    int cnt3=INF;

    vis[u]=true;
    for (i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i];
        if (vis[v]) continue;

        dfs(v);

        cnt0+=dp[v][0];
        tmp=min(dp[v][1],dp[v][2])-dp[v][0];
        if (tmp<cnt1)
        {
            cnt2=cnt1;
            cnt1=tmp;
        }
        else if (tmp<cnt2) cnt2=tmp;
        if (dp[v][2]-dp[v][0]<cnt3) cnt3=dp[v][2]-dp[v][0];
    }

    if (cnt0<dp[u][1])             dp[u][1]=cnt0;
    if (cnt0+cnt1<dp[u][2])        dp[u][2]=cnt0+cnt1;
    if (cnt0+cnt1+cnt2<dp[u][0])   dp[u][0]=cnt0+cnt1+cnt2+1;
    if (cnt0+cnt3<dp[u][0])        dp[u][0]=cnt0+cnt3+1;

}

int main()
{
    int i,u,v;

    scanf("%d",&n);
    for (i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    memset(dp,1,sizeof(dp));
    dfs(1);
    if (dp[1][0]>n) printf("-1
");
    else            printf("%d
",dp[1][0]);

    return 0;
}

ZOJ1234 단순 선형 DP(스크롤 배열)
원본 데이터의 젓가락 길이를 길게 눌러서 짧게 저장한 후,
dp[i][j][0](i>=3*j)를 전 i개의 젓가락으로 나누어 j조의 최소badness와 i개의 젓가락을 사용하지 않는다.pp[i][j][1](i>=3*j)는 전 i개의 젓가락을 j조의 최소badness와 i개의 젓가락으로 나눈다.
dp[i][j][0]=min{dp[i-1][0], dp[i-1][1];dp[i][j][1]=min{ dp[i-2][0],dp[i-2][j-1][1] }+(a[i-1]-a[i])^2; 
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int a[5005],dp[3][1002][2];

int main()
{
    int n,m,i,j,c,k1,k2,T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&m,&n);
        m+=8;
        for (i=n; i; i--) scanf("%d",&a[i]);

        memset(dp,0x7f,sizeof(dp));
        dp[0][1][1]=(a[2]-a[3])*(a[2]-a[3]);
        for (i=0; i<=2; i++) dp[0][0][0]=dp[i][0][1]=0;

        for (i=4; i<=n; i++)
        {
            c=i%3; k1=(c+2)%3; k2=(c+1)%3;
            for (j=1; j<=i/3 && j<=m; j++)
            {
                dp[c][j][0]=min(dp[k1][j][0],dp[k1][j][1]);
                dp[c][j][1]=min(dp[k2][j-1][0],dp[k2][j-1][1])+(a[i-1]-a[i])*(a[i-1]-a[i]);
            }
        }
        printf("%d
",min(dp[c][m][0],dp[c][m][1]));
    }
    return 0;
}

POJ1947 트리 DP+ 가방
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;

const int NN=160;

vector<int> adj[NN];
bool vis[NN]={0};
bool mark[NN][NN]={0};
int n,p,dp[NN][NN];

void dfs(int u)
{
    vis[u]=true;

    int size=adj[u].size();

    dp[u][1]=size;
    mark[u][1]=true;

    for (int i=0; i!=size; i++)
    {
        int v=adj[u][i];
        if (vis[v]) continue;
        dfs(v);
        for (int j=n; j; j--)
            for (int k=1; k<j; k++) if (mark[v][k] && mark[u][j-k])
            {
                if (!mark[u][j])
                {
                    mark[u][j]=true;
                    dp[u][j]=dp[u][j-k]+dp[v][k]-2;
                }
                else if (dp[u][j]>dp[u][j-k]+dp[v][k]-2) dp[u][j]=dp[u][j-k]+dp[v][k]-2;
            }
    }
}

int main()
{
    int u,v;

    scanf("%d%d",&n,&p);
    for (int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1);

    int ans=n;
    for (int i=1; i<=n; i++) if (mark[i][p] && dp[i][p]<ans) ans=dp[i][p];
    printf("%d
",ans);

    return 0;
}

POJ1390 DP
제목: 서열 (서열 길이 l < = 200, 서열 원소 값 (원제는 작은 네모난 블록의 색) Ai < = l) 을 주고, 매번 서열에서 하위 문자열 Ai~j (문자열의 원소 색깔 일치 요구) 를 선택하여 문자열 길이의 제곱 가치를 얻은 다음, 문자열을 원 서열에서 삭제할 수 있습니다. (서열에 남은 원소가 합쳐져 순서가 변하지 않습니다.)서열이 끝날 때까지 문자열을 반복해서 찾으십시오. 얻을 수 있는 최대 가치를 물어보십시오.
우선 서열을 원소에 두 개의 속성 (색 a, 개수 c) 이 있는 새로운 서열로 바꿉니다.하는 과정에서 원래 2차원 상태를 설계했는데 나중에 잘 안 되는 것을 발견했다.하나의 문자열을 제거한 후에 같은 색의 요소를 합칠 수 있음을 감안하면 마지막에 함께 삭제한 문자열이 가장 원시적인 서열에서 반드시 연속적인 것은 아니다. 여기서 내가 말한 연속적인 뜻은 다음과 같다. 예를 들어 {1 2 1 2 1 2 2 1}, 가장 좋은 방법은 중간에 있는 1을 먼저 취하고 4개의 2를 취하며 마지막에 양쪽에 있는 2개의 1을 같이 취하는 것이다.마지막 단계에서 얻은 2개의 1은 원 서열의 중간에 1이 하나 더 있는데, 즉 이 두 개의 1이 연속되지 않는다는 것이다.서열이 더욱 복잡할 때 가장 좋은 해석에서 어느 단계에서 얻은 문자열의 위치는 여러 가지 상황이 있다. 2차원 상태(dp[i][j]는 새로운 서열 i에서 j로 얻은 가치를 나타낸다)는 정보가 너무 적기 때문에 옮길 때 얻은 문자열의 위치에 따라 가능한 모든 조합을 열거해야 하기 때문에 매우 복잡하다.아마도 많은 사람들이 나와 같은 생각을 하고 있을 것이다.가비도 생각했지만 어디서부터 손을 대야 할지 모르겠다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

typedef pair<int, int> pii;

const int N = 210;

int n, a[N], c[N], last[N], prev[N], dp[N][N][N];

void init() {
	int x, y = -1, k = 0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (x == y) c[k-1]++;
		else a[k]= x, c[k++] = 1;
		y = x;
	}
	n = k;

	memset(last, -1, sizeof(last));
	for (int i = 0; i < n; i++) {
		prev[i] = last[a[i]];
		last[a[i]] = i;
	}
	memset(dp, -1, sizeof(dp));
}

int DP(int i, int j, int k) {
	if (dp[i][j][k] != -1) return dp[i][j][k];
	if (i > j) return dp[i][j][k] = -10000000;

	if (i == j) return dp[i][j][k] = (c[i]+k) * (c[i]+k);

	int ret = DP(i, j-1, 0) + (c[j]+k) * (c[j]+k);
	for (int p = prev[j]; p >= i; p = prev[p]) {
		int tmp = DP(i, p, c[j]+k) + DP(p+1, j-1, 0);
		ret = max(ret, tmp);
	}
	return dp[i][j][k] = ret;
}

int main() {
	int cas;
	cin >> cas;
	for (int i = 0; i < cas; i++) {
		init();
		cout << "Case " << i+1 << ": " << DP(0, n-1, 0) << endl;
	}
	return 0;
}

계속
HDU 4632 Palindrome subsequence(구간 DP)
POJ 1947 Rebuilding Roads(트리 DP)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage