DP 3개

곧 아껴야겠네,,,, 빨리 돌파해야할텐데,, 오늘의 dp는 아직 물 문제야...Noip: 김명의 예산안.아마 의존하는 가방이 있을 거예요. 이 가방은 전체적으로 선택하든 안 선택하든 부분적으로 선택하지 않으면 돼요.

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define Rep(i,n) for(int i = 1; i <= n ; i ++)
#define RepG(i,x) for(int i = head[x] ;~ i ; i = edge[i].next)
#define Rep_d(i,n) for(int i = n ; i > 0 ; i --)
#define Rep_0(i,n) for(int i = 0 ; i < n ; i ++)
#define RD(i,x,n) for(int i = x; i <= n ; i ++)
#define CLR(a,b) memset(a,b,sizeof(a))
#define fl edge[i].f
#define vfl edge[i^1].f
#define v edge[i].to
using namespace std;
const int inf = 1 << 30;
typedef long long ll;
int read(){
    char ch = getchar();
    while(ch < '0' || ch > '9')ch = getchar ();
    int x = 0;
    while(ch >= '0' && ch <= '9')x = 10 * x + ch - '0',ch = getchar ();
    return x;
}
int n,m;
int f[20005];
int link[65][5];
int c[65],w[65],ct[65];
int main()
{
    CLR(link,-1);
    n = read();
    n /= 10;
    m = read();
    Rep(i,m){
        w[i] = read(),w[i] /= 10,c[i] = read(),c[i] *= w[i];
        link[i][0] = read();
    }
    CLR(ct,0);
    Rep(i,m)
        if(link[i][0])link[link[i][0]][++ ct[link[i][0]]] = i;

//  Rep(i,m)
//      printf("%d %d %d %d
",link[i][0],link[i][1],link[i][2],c[i]);
    Rep(i,m)
        for(int j = n;j >= w[i];j --){
            if(!link[i][0]){
                f[j] = max(f[j],f[j - w[i]] + c[i]);
                if(ct[i] >= 1 && j >= w[i] + w[link[i][1]])f[j] = max(f[j - w[i] - w[link[i][1]]] + c[i] + c[link[i][1]],f[j]);
                if(ct[i] == 2){
                    if(j >= w[i] + w[link[i][1]] + w[link[i][2]])f[j] = max(f[j - w[i] - w[link[i][1]] - w[link[i][2]]] + c[i] + c[link[i][1]] + c[link[i][2]],max(f[j - w[i] - w[link[i][2]]] + c[i] + c[link[i][2]],f[j]));       
                    else if(j >= w[i] + w[link[i][2]])f[j] = max(f[j],f[j - w[i] - w[link[i][2]]] + c[i] + c[link[i][2]]);      
                }
            }
        }
    printf("%d
",f[n] * 10);
    return 0;
}

2. 더 물오른 거북이 바둑: 카드의 개수를 통계하고 01배낭과 유사하게 이 카드를 선택하든지 말든지 고려한다.

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define Rep(i,n) for(int i = 1; i <= n ; i ++)
#define Repp(i,n) for(int i = 0;i <= n ; i ++)
#define RepG(i,x) for(int i = head[x] ;~ i ; i = edge[i].next)
#define Rep_d(i,n) for(int i = n ; i > 0 ; i --)
#define Rep_0(i,n) for(int i = 0 ; i < n ; i ++)
#define RD(i,x,n) for(int i = x; i <= n ; i ++)
#define CLR(a,b) memset(a,b,sizeof(a))
#define fl edge[i].f
#define vfl edge[i^1].f
#define v edge[i].to
#define N 355
using namespace std;
const int inf = 1 << 30;
typedef long long ll;
int read(){
    char ch = getchar();
    while(ch < '0' || ch > '9')ch = getchar ();
    int x = 0;
    while(ch >= '0' && ch <= '9')x = 10 * x + ch - '0',ch = getchar ();
    return x;
}
int n ,m,seq[N],c[6];
int f[41][41][41][41];
int main()
{
    n = read(),m = read();
    Rep(i,n)
        seq[i] = read();
    Rep(j,m){
        int p = read();
        c[p] ++;
    }
    f[0][0][0][0] = seq[1];
    Repp(i,c[1])
        Repp(j,c[2])
            Repp(k,c[3])
                Repp(l,c[4])
                {
                //  printf("i : %d j : %d k : %d l : %d
",i,j,k,l);
                    int len = i + j * 2 + k * 3 + l * 4 + 1;
                    if(i >= 1)f[i][j][k][l] = max(f[i - 1][j][k][l] + seq[len],f[i][j][k][l]);
                //  printf("%d ",f[i][j][k][l]);
                    if(j >= 1)f[i][j][k][l] = max(f[i][j - 1][k][l] + seq[len],f[i][j][k][l]);
                //  printf("%d ",f[i][j][k][l]);
                    if(k >= 1)f[i][j][k][l] = max(f[i][j][k - 1][l] + seq[len],f[i][j][k][l]);
                //  printf("%d ",f[i][j][k][l]);
                    if(l >= 1)f[i][j][k][l] = max(f[i][j][k][l - 1] + seq[len],f[i][j][k][l]);
                //  printf("%d
",f[i][j][k][l]);
                }
    printf("%d
",f[c[1]][c[2]][c[3]][c[4]]);
    return 0;
}

3. 앞의 검색은 가지치기, 작은 요정들이 함께 베낀다. 그러나 어떤 것은 충돌이 발생하여 하나의 집합이 되지 않는다. 글씨가 예쁜 것도 있고 예쁘지 않은 것도 있다. 가장 많은 미관을 얻을 수 있느냐고 묻는다.데이터 크기: N<= 100;직접 수색 시간 초과, 아주 명백한 가지치기: 이후의 모든 작은 정령의 필적 미관도와 <=ans는 이 점,,

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define Rep(i,n) for(int i = 1; i <= n ; i ++)
#define RepG(i,x) for(int i = head[x] ;~ i ; i = edge[i].next)
#define Rep_d(i,n) for(int i = n ; i > 0 ; i --)
#define Rep_0(i,n) for(int i = 0 ; i < n ; i ++)
#define RD(i,x,n) for(int i = x; i <= n ; i ++)
#define CLR(a,b) memset(a,b,sizeof(a))
#define fl edge[i].f
#define vfl edge[i^1].f
#define v edge[i].to
#define N 65
using namespace std;
const int inf = 1 << 30;
typedef long long ll;
int read(){
    char ch = getchar();
    while(ch < '0' || ch > '9')ch = getchar ();
    int x = 0;
    while(ch >= '0' && ch <= '9')x = 10 * x + ch - '0',ch = getchar ();
    return x;
}
struct Edge{int next,to;}edge[100005];
int ans = 0,n,head[N],ct[N],val[N],cnt = 0;
void save(int a,int b){
    edge[cnt].next = head[a];
    edge[cnt].to = b;
    head[a] = cnt ++;
}
void dfs(int s,int sum){
    int m ;
    ans = max(ans,sum);
    RD(x,s,n){
        if(!ct[x]){
            m = 0;
            RepG(i,x)
                ct[v] ++;
            RD(i,x + 1,n)if(!ct[i])m += val[i];
            if(m + sum + val[x] <= ans){
                RepG(i,x)
                    ct[v] --;
                continue;
            }
            ct[x] = 1;
            dfs(x + 1,sum + val[x]);
            ct[x] = 0;
            RepG(i,x)
                ct[v] --;
        }
    }
}
int main()
{
    CLR(head,-1);
    n = read();
    Rep(i,n)val[i] = read();
    int a,b;
    while(~scanf("%d%d",&a,&b))
        save(a,b),save(b,a);
    dfs(1,0);
    printf("%d
",ans);
    return 0;
}