NOI 2019シンクロ戦day 1

T1
帰り道==帰り道?
問題は臭くて長い.の
まずデータの範囲を見て、A=B=Cの部分は何ですか?一番早い到着時間は?A=B=0でDpできるみたい?
後に、時間複雑度玄学のDP dp[u][t]は、時間tにおいてuに到達する最小代価dp[u][t]は、時間tにおいてuに到達する最小代価dp[u][t]は、時間tにおいてuに到達する最小代価遷移方程式を表す:dp[u][t]=d p[v][q[i]+F(p[i]−t)dp[u][t]=dp[v]+F(p[i]−t]=dp[v][q[i]+F(p[i]−t)境界:d p[u][t]=t dp[u][t]=t dp[u][t]=t 70%の範囲で走るのが速い
Code:

#include 
#define maxn 2010
#define maxt 1010
#define maxm 200010
#define LL long long
using namespace std;
const LL inf = 1e12;
struct Edge{
	int to, next, p, q;
}edge[maxm];
int num, head[maxn], n, m, A, B, C; 
LL dp[maxn][maxt];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int p, int q){ edge[++num] = (Edge) { y, head[x], p, q }; head[x] = num; }
LL F(int x){ return 1LL * A * x * x + B * x + C; }

void dfs(int u, int t){
	if (u == n) dp[u][t] = t;
	if (dp[u][t] < inf) return;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to; 
		if (edge[i].p >= t){
			dfs(v, edge[i].q);
			dp[u][t] = min(dp[u][t], dp[v][edge[i].q] + F(edge[i].p - t));
		}
	}
}

int main(){
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
	n = read(), m = read(), A = read(), B = read(), C = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read(), p = read(), q = read();
		addedge(x, y, p, q);
		dp[y][q] = inf;
	}
	dp[1][0] = inf;
/*	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= 1000; ++j) dp[i][j] = inf;*/
	dfs(1, 0);
	printf("%lld
", dp[1][0]);
	return 0;
}

T2
20%の暴力は適当に打って規則を探して失敗することを望んでこの問題はあまり考えていないで、このようにしました
Code:

#include 
#define maxn 310
#define qy 1000000007
using namespace std;
int a[maxn], b[maxn], ans, n, num[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void Do(){
	for (int s = 1; s <= n; ++s){
		int x = 0, i = s - 1;
		while (i >= 1 && num[i] <= num[s]) ++x, --i;
		int y = 0, j = s + 1;
		while (j <= n && num[j] < num[s]) ++y, ++j;
		if (abs(x - y) > 2) return;
	}
	(++ans) %= qy;
}

void dfs(int k){
	if (k > n) Do(); else{
		for (int i = a[k]; i <= b[k]; ++i){
			num[k] = i;
			dfs(k + 1);
		}
	}
}

int main(){
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = read();
	dfs(1);
	printf("%d
", ans);
	return 0; 
}

T3
すぐに28分O(n 4)の水d p O(n^4)を設計した水dp O(n 4)の水dp d p[i][s l][k 1][k 2]はi位を表し、合計s l位は同じで、それぞれk 1をとり、k 2個のdp[i][sl][k 1][k 2]はi位を表し、合計sl位は同じで、それぞれk 1を取り、k 2個のdp[i][sl][k 1][k 2]はi位を表し、合計sl位は同じで、それぞれk 1を取り、k 2個の転移方程式:dp[i][s l][k 1][k 2]=m a x(dp[i−1][s l−1][s l−1][k 1−1][k 2−1][k 2−1]+a[i]+b[i],d p[i−1][s l][k 1−1][k 1][k 2][k 2]+a[i],dp[i−1][s l][k 1][k 1][k 1][k 1][k 1][k 1]+b[i],dp[i−1][s l][k 1][k 1][k 2])dp[[k[k[k[k[k 2][k 2][k 2])sl][k 1][k 2]=max(dp[i-1][sl-1][k 1-1][k2-1]+a[i]+b[i],dp[i-1][sl][k1-1][k2]+a[i],dp[i-1][sl][k1][k2-1]+b[i],dp[i-1][sl][k1][k2]) dp[i][sl][k1][k2]=max(dp[i−1][sl−1][k1−1][k2−1]+a[i]+b[i],dp[i−1][sl][k1−1][k2]+a[i],dp[i−1][sl][k1][k2−1]+b[i],dp[i−1][sl][k1][k2]) A N S = m a x ( d p [ n ] [ i ] [ k ] [ k ] ) ( l < = i < = k ) ANS=max(dp[n][i][k][k])(l<=i<=k) ANS=max(dp[n][i][k][k])(l<=i<=k)
Code:

#include 
#define LL long long
#define maxn 32
using namespace std;
int n, K, L;
LL dp[2][maxn][maxn][maxn], a[maxn], b[maxn];

inline LL read(){
	LL s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	int M = read();
	while (M--){
		n = read(), K = read(), L = read();
		for (int i = 1; i <= n; ++i) a[i] = read();
		for (int i = 1; i <= n; ++i) b[i] = read();
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; ++i){
			int p = i & 1;
			for (int j = 0; j <= K; ++j)	
				for (int k = j; k <= K; ++k)
					for (int l = j; l <= K; ++l){
						dp[p][j][k][l] = dp[p ^ 1][j][k][l];
						if (j && k && l) dp[p][j][k][l] = max(dp[p][j][k][l], dp[p ^ 1][j - 1][k - 1][l - 1] + a[i] + b[i]);
						if (k) dp[p][j][k][l] = max(dp[p][j][k][l], dp[p ^ 1][j][k - 1][l] + a[i]);
						if (l) dp[p][j][k][l] = max(dp[p][j][k][l], dp[p ^ 1][j][k][l - 1] + b[i]);
					}
		}
		int p = n & 1;
		LL ans = 0; 
		for (int i = L; i <= K; ++i) ans = max(ans, dp[p][i][K][K]); 
		printf("%lld
", ans);
	}
	return 0;
}

いつ成績が発表されるか分からない...期待得点70+20+28=118