Untitled
unknown
plain_text
2 years ago
7.0 kB
7
Indexable
#include <iostream>
using namespace std;
int N,linh_kien[21];
int voucher,so_luong,giam_gia[31][21];
int mua,TT[21];
int gia,visit[21];
int a,gia_cho_troi;
int result = 10000000;
int count1[21];
int TG = 0 ;
void backtrack (int vt){
if(vt == voucher){
int gia_cho_troi = 0;
for(int i = 1; i <= mua; i++){
if(visit[TT[i]] == 0){
gia_cho_troi += linh_kien[TT[i]];
}
}
if(TG + gia_cho_troi < result) result = TG + gia_cho_troi;
return;
}
for(int i= 0; i< 2; i++){
if(i == 0 ) backtrack(vt+1);
else{
for(int j = 1; j <= giam_gia[vt][2];j++){
visit[giam_gia[vt][j+2]] ++;
}
TG += giam_gia[vt][1];
if(result > TG) backtrack(vt+1);
TG -= giam_gia[vt][1];
for(int j = 1; j <= giam_gia[vt][2];j++){
visit[giam_gia[vt][i+2]] --;
}
}
}
}
int main(){
freopen ("Text.txt","r",stdin);
int T; cin >> T;
for(int tc = 1; tc <= T; tc ++){
cin >> N;
for(int i = 1; i <= N; i++){
cin >> linh_kien[i];
visit[i] = 0;
}
cin >> voucher ;
for(int i = 1; i <= voucher;i++){
count1[i] = 0;
cin >> giam_gia[i][1] >> giam_gia[i][2];
for(int j = 1; j <= giam_gia[i][2] ; j++){
cin >> giam_gia[i][j+2];
}
}
cin >> mua;
for(int i = 1; i <= mua;i++){
cin >> TT[i];
}
result = 1000000 ;
TG = 0;
backtrack(0);
cout << "#" << tc << " " << result << endl;
}
return 0;
}
minimal
#include<iostream>
using namespace std;
int main()
{
int test_case;
int T, k, n;
int arr[100000];
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> k >> n;
int sum1 = 0;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
int max = 0;
for(int i = 0; i < n; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
while(true) {
int sum = 0;
int cnt = 0;
for(int i = 0; i < n; i++) {
sum += arr[i];
if (sum>max) {
cnt++;
sum = arr[i];
}
}
if(cnt < k) {
break;
} else {
max++;
}
}
cout << "#" << test_case << " " << max << endl;
}
return 0;
}
/*#include<iostream>
using namespace std;
int main()
{
int test_case;
int T, k, n;
int arr[100000];
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> k >> n;
int sum1 = 0;
for(int i = 0; i < n; i++) {
cin >> arr[i];
sum1 += arr[i];
}
int max = 0;
for(int i = 0; i < n; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
int check = (sum1 + max) / 2;
while(true) {
if (sum1 <= max) {break;}
int sum = 0;
int cnt = 0;
for(int i = 0; i < n; i++) {
sum += arr[i];
if(sum > check) {
cnt++;
sum = arr[i];
}
}
if(cnt < k) {
sum1 = check;
check = (sum1 + max) / 2;
} else {
max = check + 1;
check = (sum1 + max) / 2;
}
}
cout << "#" << test_case << " " << check << endl;
}
return 0;
}*/
hugo dao vang
#include <iostream>
#pragma warning(disable:4996)
using namespace std;
int qx[1000], qy[1000], f = -1, r = -1;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void Push(int x, int y) {
r++;
qx[r] = x;
qy[r] = y;
}
void Pop(int& x, int& y) {
f++;
x = qx[f];
y = qy[f];
}
void Reset() {
f = r = -1;
}
bool isEmpty() {
return f == r;
}
int n, m, g;
int map[50][50];
int visit[50][50];
int gm[101][3];
int kq[101][3];
int minPath,maxGm,curGm,curPath;
void saveKq() {
for (int i = 1; i <= g; i++) {
kq[i][0] = gm[i][0];
kq[i][1] = gm[i][1];
kq[i][2] = gm[i][2];
}
}
void setVisitGm(int x, int y) {
for (int i = 1; i <= g; i++) {
if (x == gm[i][0] && y == gm[i][1]) {
gm[i][2] = 1;
break;
}
}
}
void resetVisit() {
for (int i = 1; i <= g; i++) gm[i][2] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
visit[i][j] = -1;
}
}
}
void bfs(int r, int c) {
Reset();
Push(r, c);
visit[r][c] = 0;
curGm = 0;
curPath = 0;
while (!isEmpty()) {
int x, y;
Pop(x, y);
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && visit[xx][yy] == -1 && map[xx][yy]!=0) {
Push(xx, yy);
visit[xx][yy] = visit[x][y] + 1;
if (map[xx][yy] == 2) {
curGm++;
setVisitGm(xx, yy);
curPath = max(curPath, visit[xx][yy]);
}
}
}
}
}
int main() {
freopen("Text.txt", "r", stdin);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> n >> g;
for (int i = 1; i <= g; i++) {
cin >> gm[i][0] >> gm[i][1];
gm[i][2] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> map[i][j];
}
}
for (int i = 1; i <= g; i++) {
map[gm[i][0]][gm[i][1]] = 2;
}
maxGm = 0;
minPath = 1e9;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j] == 1) {
resetVisit();
bfs(i, j);
if (curGm > maxGm) {
maxGm = curGm;
minPath = curPath;
saveKq();
}
else if (curGm == maxGm && curPath != 0) {
if (curPath < minPath) {
minPath = curPath;
saveKq();
}
}
}
}
}
cout << "Case #" << t << endl;
if (minPath == 1e9) {
cout << -1 << endl;
}
else {
cout << minPath << endl;
for (int i = 1; i <= g; i++) {
if (kq[i][2] == 0) {
cout << kq[i][0] << " " << kq[i][1] << endl;
}
}
}
}
return 0;
}
tan cong thanh tri
#include <iostream>
using namespace std;
int n,thanh,so_may_bd,thanh_lk;
int array[110][110];
int dinh[110],ban_da[110],flag;
int result;
void DFS(int temthanh,int thanh, int sl, int min, int d1, int d2){
if(temthanh == thanh && sl >= 3){
flag = 1;
result += min;
array[d1][d2] = 0;
array[d2][d1] = 0;
return;
}
for(int i = 0; i < n; i++){
if(flag == 1) return;
if(array[temthanh][i] == 1 && (dinh[i] == 0 || (i == thanh && sl >= 3))){
dinh[i] = 1;
int value = ban_da[temthanh] + ban_da[i];
if(min > value){
DFS(i,thanh,sl+1,value,temthanh,i);
}
else DFS(i,thanh,sl+1,min,d1,d2);
}
}
}
int main (){
freopen ("Text.txt","r",stdin);
int T; cin >> T;
for(int tc = 1 ; tc <= T; tc++){
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
array[i][j] = 0;
dinh[j] = 0;
}
}
for(int i = 0; i < n; i ++){
cin >> thanh >> so_may_bd >> thanh_lk;
ban_da[thanh] = so_may_bd;
for(int j = 0; j < thanh_lk; j++){
int c;
cin >> c;
array[thanh][c] = 1;
array[c][thanh] = 1;
}
}
result = 0;
for(int i = 0; i < n ; i++){
for(int j = 0; j < n; j++){
dinh[j] = 0;
}
dinh[i] = 1;
flag = 0;
DFS(i,i,1,1000000,-1,-1);
}
cout << result << endl;
}
return 0;
}
Editor is loading...