srm588 div1

어, 한 문제 냈어. 한 문제는 시스템 테스트에서 지워졌어. 오늘 보니까 니마가 머리가 나빠졌어. 왜 두 번째 문제가 dp라고 생각했는지 이해가 안 돼...
그래.
A문제, 할 말 없어요. 순서를 정하고 아무렇게나 dp로 내리면 돼요. 순서를 정한 후에 시작점과 끝점 토니의 차이를 선택한 숫자의 합은 정해진 거예요.

#include <algorithm>
#include <vector>
using namespace std;

typedef struct
{
    int d,t;
}Song;


    bool cmp(Song x,Song y)
    {
        if (x.t!=y.t) return x.t<y.t;
        return x.d<y.d;
    }

    bool cmp1(Song x,Song y)
    {
        if (x.d!=y.d) return x.d<y.d;
        return x.t<y.t;
    }


class GUMIAndSongsDiv1
{
public:

    Song a[55];
    Song b[55];




    int maxSongs(vector <int> duration, vector <int> tone, int T)
    {
        int i,j,k,n;
        n=duration.size();
        for (i=0;i<n;i++)
        {
            a[i].d=duration[i];
            a[i].t=tone[i];
            b[i]=a[i];
        }
        sort(a,a+n,cmp);
        sort(b,b+n,cmp1);
        int ans=0;
        for (i=0;i<n;i++)
        {
            for (j=i;j<n;j++)
            {
                int cnt=0,t;
                t=a[j].t-a[i].t;
                for (k=0;k<n;k++)
                {
                    if (b[k].t>=a[i].t && b[k].t<=a[j].t)
                    {
                        if (b[k].d+t>T) continue;
                        cnt++;
                        t+=b[k].d;
                    }
                }
                ans=max(ans,cnt);
            }
        }

        return int(ans) ;
    }
};

B문제, 어, 그런데 어떤 문을 열고 총 열쇠가 정해져서 흰 열쇠가 가장 많고 나머지는 빨간 열쇠를 기록하고 검색하면 된다고...

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
using namespace std ;
#define For(i , n) for(int i = 0 ; i < (n) ; ++i)
#define SZ(x)  (int)((x).size())
typedef long long lint ;
const int maxint = -1u>>2 ;
const double eps = 1e-6 ;

typedef struct
{
    int r,g,w,state;
}Key;

queue<Key> q;
int vis[(1<<12)+5][125];

class KeyDungeonDiv1
{
public:
int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys)
{
    int i,j,n,ans;
    n=doorR.size();
    memset(vis,0,sizeof(vis));
    Key tmp;
    tmp.r=keys[0];
    tmp.g=keys[1];
    tmp.w=keys[2];
    tmp.state=0;
    q.push(tmp);
    ans=0;
    while(!q.empty())
    {
        tmp=q.front();
        q.pop();
        if (vis[tmp.state][tmp.r]==1) continue;
        vis[tmp.state][tmp.r]=1;
        ans=max(ans,tmp.g+tmp.w+tmp.r);
        i=tmp.state;
        for (j=0;j<n;j++)
        {
            if ((i & (1<<j))!=0) continue;
            int lr=max(0,doorR[j]-tmp.r);
            int lg=max(0,doorG[j]-tmp.g);
         //   printf("%d %d %d %d
",i,j,doorR[j],dp[i].r);
            if (lr+lg>tmp.w) continue;
            Key tmp1;
            tmp1.r=max(0,tmp.r-doorR[j])+roomR[j];
            tmp1.g=max(0,tmp.g-doorG[j])+roomG[j];
            tmp1.w=tmp.w-(lr+lg)+roomW[j];
            int p=(i | (1<<j));
            tmp1.state=p;
            q.push(tmp1);
        }
    }

return int(ans);
}
};