ABC E求调
  • 板块学术版
  • 楼主_I_AK_NOI_
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/9/30 21:43
  • 上次更新2023/11/2 16:53:43
查看原帖
ABC E求调
671902
_I_AK_NOI_楼主2023/9/30 21:43

RT,状压,一直错三个

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[105][1000005];
signed main(){
    int n , k , p;
    cin >> n >> k >> p;
    vector <int> c(n + 1);
    vector < vector <int> > a(n + 1 , vector <int> (k + 1));
    for(int i = 1;i <= n;i++){
		cin >> c[i];
		for(int j = 1;j <= k;j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0;i < 105;i++){
		for(int j = 0;j < 1000005;j++){
			dp[i][j] = 1e18;
		}
	}
	dp[0][0] = 0;
	for(int i = 0;i <= n;i++) dp[i][0] = 0;
	
	for(int i = 1;i <= n;i++){
		for(int j = 0;j <= 55555;j++){
			dp[i][j] = dp[i - 1][j];
		}
		for(int j = 0;j <= 55555;j++){
			vector <int> w(6);
			w[1] = j / 10000;
			w[2] = j / 1000 % 10;
			w[3] = j / 100 % 10;
			w[4] = j / 10 % 10;
			w[5] = j % 10;
			for(int l = 1;l <= k;l++){
				int pos = l + p - k;
				w[pos] += a[i][l];
				w[pos] = min(w[pos] , p);
			}
			int tmp = 0;
			for(int ww = p , www = 1;ww >= 1;ww-- , www *= 10){
				tmp += w[ww] * www;
			}
			dp[i][tmp] = min(dp[i][tmp] , dp[i - 1][j] + c[i]);
		}
	}
	int uuu = 0;
	for(int i = 1;i <= k;i++){
		uuu *= 10;
		uuu += p;
	}
	int ans = 1e18;
	for(int i = 0;i <= n;i++){
		ans = min(ans , dp[i][uuu]);
	}
	cout << (ans >= 1e17 ? -1 : ans);
    return 0;
}
2023/9/30 21:43
加载中...