2019 hdu 다 교 첫 번 째 A 문제 Blank(dp,시공 간 최적화)

http://acm.hdu.edu.cn/showproblem.php?pid=6578
제목 설명
There are N blanks arranged in a row. The blanks are numbered 1,2,…,N from left to right. Tom is filling each blank with one number in {0,1,2,3}. According to his thought, the following M conditions must all be satisfied. The ith condition is: There are exactly xi different numbers among blanks ∈[li,ri]. In how many ways can the blanks be filled to satisfy all the conditions? Find the answer modulo 998244353.
 
 
입력
The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases. In each test case, there are two integers n(1≤n≤100) and m(0≤m≤100) in the first line, denoting the number of blanks and the number of conditions. For the following m lines, each line contains three integers l,r and x, denoting a condition(1≤l≤r≤n, 1≤x≤4).
 
출력
For each testcase, output a single line containing an integer, denoting the number of ways to paint the blanks satisfying all the conditions modulo 998244353.
 
샘플 입력
샘플 데이터 복사

2
1 0
4 1
1 3 3

샘플 출력

4
96

T 조 샘플,
길이 n 의 서열 종 수 를 구하 라 고 합 니 다.(m 개의 제한 이 있 습 니 다.[li,ri]구간 에 있 고 xi 종 수 만 있 습 니 다.)pos
소박 한 생각,dp[len][p0][p1][p2][p3],길 이 는 len 의 서열,마지막 0 의 하 표 는 p0,마지막 1 의 하 표 는 p1,...
시간 문 제 를 고려 하지 않 으 면 메모리 가 부족 하 다 는 것 이 분명 하 다.
길이 가 len 인 서열 은 길이 가 len-1 인 서열 에서 밀 려 온 것 이 분명 하기 때문에 1 차원 은 01 로 굴 러 갈 수 있 습 니 다.
또한 길이 가 len 인 서열 이 라면 p0,p1,p2,p3 중 하 나 는 len 이 어야 합 니 다.우 리 는 이 를 1 차원 과 합병(공용)하 는 것 을 고려 할 수 있 습 니 다.그러나 어떤 수의 아래 표 시 는 len 일 까요?미 치 겠 습 니 다~~
분명 한 것 은 모든 p 가 실제 적 으로 아래 표 시 를 대표 하 는 것 이 아니 라 이런 수(이 수 를 사용 하지 않 았 을 때 0 을 제외 하고 사용 하면 마지막 으로 나타 난 아래 표 시 는 모두 유일한 것 이 고 한 위치 에 두 가지 수가 있 을 수 없다)를 나타 낸다.즉,몇 개의 p 가 제한 범위 안에 있 고 이 범위 안에 몇 가지 수가 있다 는 것 이다.pi 가 큰 지 pj 가 큰 지 에 관 계 없 이 우 리 는 4 개의 p 를 비 증가 순서에 따라 순 서 를 정 하고 순 서 를 정 한 후에 똑 같은 상태 로 볼 수 있다.
dp[i][j][k][t]를 정의 합 니 다.
dp[i][j][k][t]+=dp[i-1][j][k][t](아래 i 로 표 시 된 위치,놓 은 수 는 마지막 으로 나타 난 위치 아래 i-1 로 표 시 된 위치 와 같다)
dp[i][i-1][k][t]+=dp[i-1][j][k][t](아래 i 로 표 시 된 위치,놓 은 수 는 마지막 으로 나타 난 위치의 아래 j 로 표 시 된 수 와 같다)
dp[i][i-1][j][t]+=dp[i-1][j][k][t](아래 i 로 표 시 된 위치,놓 은 수 는 마지막 으로 나타 난 위치 아래 k 로 표 시 된 수 와 같 습 니 다)
dp[i][i-1][j][k]+=dp[i-1][j][k][t](아래 i 로 표 시 된 위치,놓 은 수 는 마지막 으로 나타 난 위치 아래 t 로 표 시 된 수 와 같 습 니 다)
그 다음 에 1 차원 01 스크롤 을 공간 을 2*1e6 로 최적화 시 켰 고 시간 복잡 도 는 O(n^5)에서 O(n^4)로 최적화 시 켰 다.
이것 은 제한 이 없 는 상황 인 데 제한 이 있 으 면 어떻게 합 니까?판단 을 가 하 다
하나의 아래 표 시 는 하나의 수 를 대표 하 며,각 제한 구간 의 오른쪽 점 은 i 와 같은 제한 이다.

if((1+(j>=lim[pos].l)+(k>=lim[pos].l)+(t>=lim[pos].l))!=lim[pos].x)
	dp[p][j][k][t]=0;

제한 에 부합 되 지 않 으 면 뒤에 공헌 할 수 없다.바로 0 이다.
제한 구간 오른쪽 점 이 i 구간 으로 저 장 될 때 잘 처리 해 야 합 니 다.vector 로 저장 할 수 있 습 니 다.v[i]오른쪽 점 이 i 인 모든 구간 을 저장 하면 판단 할 때 많은 시간 을 절약 할 수 있 습 니 다.

struct node{
	int l,r,x;
}lim[105];
int v[105][105],tail[105];

나 는 2 차원 배열 로 시 뮬 레이 션 한 vector,v[i]오른쪽 단점 에서 i 로 표 시 된 구간 을 lim 에서 표시 하면 아래 표 시 를 뛰 어 찾 을 수 있 습 니 다.for 순환 1~m 를 사용 하지 않 아 도 됩 니 다.
(여기 서 정렬 할 지 안 할 지 는 영향 이 없다.어차피 판단 해 야 할 구간 은 판단 해 야 지 도망 칠 수 없다.잉잉)
두 교

#include
using namespace std;
typedef long long ll;
const int mod=998244353;
int dp[2][101][101][101];
struct node{
	int l,r,x;
}lim[105];
//bool cmp(node a,node b){
//	if(a.r!=b.r) return a.r=lim[pos].l)+(k>=lim[pos].l)+(t>=lim[pos].l))!=lim[pos].x)
							dp[p][j][k][t]=0;
						}
					}
				}
			}
		}
		ll ans=0;
		for(int i=0;i