학교 식당 다 이 닝 상 압 DP

5238 단어 bzojDP상태 DP
제목: 한 학생 서열, 한 사람 에 게 먹고 싶 은 음식 t 와 참 는 정도 x 가 있 습 니 다. 먼저 그의 뒤 를 따 르 는 사람 에 게 먹 으 라 고 하면 x 개 를 초과 하지 말고 최소 의 식사 시간 을 물 어보 세 요.만약 에 j 를 먼저 하면 k 를 하고 있 습 니 다. 시간 은 (t [j] | t [k]) - (t [j] & t [k]) = = 처음에 그 바짝 따 르 는 것 을 보지 못 해서 저 는 n ^ 3 * 7 의 알고리즘 을 썼 습 니 다. 그 결과 T 를 오랫동안 생각 했 습 니 다. 어떻게 해 야 할 지 몰 랐 습 니 다. 그리고 문 제 를 살 펴 보 았 는데 문 제 를 잘못 보 았 습 니 다.이런 문제 의 방식 은 공헌 이 이웃 과 관련 된 것 을 보면 결말 상 태 를 설정 해 야 한다. 그러면 f [i] [j] [k] 는 i 번 째 사람 까지 하 겠 다 고 밝 혔 다. 그의 엉덩이 뒤의 7 명의 상 태 는 j 이 고 01 은 먹 을 지 여 부 를 나타 내 며 k 는 지난 결말 과 현재 의 거 리 를 나타 낸다.그러면 j 상 태 는 현재 위치 도 표시 하고 처리 하기 편리 하 다. 그리고 j & 1 일 때 i 가 이미 먹었다 는 것 을 설명 한다.그러면 f [i + 1] [j > 1] [k - 1] = min (f [i] [j] [k]) 이 있 습 니 다. 그렇지 않 으 면 저 는 뒤에 있 는 7 명 중에서 어떤 사람 이 먹 었 는 지 일일이 계산 하고 공헌 을 계산 합 니 다.f [i] [j | (1 < 우선 순위 에 주의 하 세 요. 괄호 쓰기 가 귀 찮 습 니 다. 비트 연산 의 우선 순위 가 가장 낮 습 니 다. 그리고 WA 가 시원 하 게 되 었 습 니 다. 마지막 으로 C + 의 배열 이 마이너스 가 될 수 없다 는 것 을 알 게 되 었 습 니 다. 그러면 + 개 10 이면 됩 니 다.
#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e3+5;
const int MAX=10;
int n,m,inf;
int f[N][256][50];
struct node
{
    int t,b;
}a[N];
int main()
{
    int cas;
    scanf("%d",&cas);
    while (cas--)
    {
        scanf("%d",&n);
        fo(i,1,n)
        {
            scanf("%d%d",&a[i].t,&a[i].b);
        }
        memset(f,0x3f,sizeof(f));
        inf=f[1][0][-1+MAX];
        int tot=1<<8;
        f[1][0][-1+MAX]=0;
        fo(i,1,n)
        {
            fo(j,0,tot-1)
            {
                fo(k,-8,7)
                if (f[i][j][k+MAX]if (j&1)
                    {
                        f[i+1][j>>1][k-1+MAX]=min(f[i+1][j>>1][k-1+MAX],f[i][j][k+MAX]);
                    }
                    else
                    {
                        int r=inf;
                        fo(l,0,7)
                        {
                            if ((j&(1<0)
                            {
                                if (i+l>r)break;
                                r=min(r,i+l+a[i+l].b);
                                int tmp;
                                if (!(i+k))tmp=0;
                                else tmp=a[i+k].t^a[i+l].t;
                                f[i][j+(1<1<int ans=inf;
        fo(i,-8,-1)
        {
            ans=min(ans,f[n+1][0][i+MAX]);
        }
        printf("%d
"
,ans); } }

좋은 웹페이지 즐겨찾기