#include <stdio.h> #include <algorithm> using namespace std; /* Codeforces */ /*****************************************************************************/ int main(void) { int n, a; long long m=0, s=0; scanf("%d", &n); for (int i=0; i<n; i++) { scanf("%d", &a); s+=a; m=max(m, (long long)a); } long long l=0, h=2e9+1, ans; while (l<=h) { long long mid=(l+h)/2; if (mid*(n-1)>=s) { h=mid-1; ans=mid; } else l=mid+1; } printf("%I64d\n", max(m, ans)); return 0; } /*****************************************************************************/
Codeforces 202 DIV2 C
简单的二分查找:..
Codeforces 202 DIV2 B
又是简单贪心:..
#include <stdio.h> #include <climits> #include <algorithm> using namespace std; /* Codeforces */ /*****************************************************************************/ int main(void) { int v, d[10], n, m=INT_MAX; scanf("%d", &v); for (int i=1; i<=9; i++) { scanf("%d", &d[i]); m=min(m, d[i]); } if (m>v) puts("-1"); else { n=v/m; while (n--) for (int i=9; i>0; i--) if (v>=d[i]&&(v-d[i])/m==n) { printf("%d", i); v-=d[i]; break; } puts(""); } return 0; } /*****************************************************************************/
Codeforces 202 DIV2 A
简单贪心:..
#include <stdio.h> using namespace std; /* Codeforces */ /*****************************************************************************/ int main(void) { int n, r, t[2]={}; scanf("%d", &n); for (int i=0; i<n; i++) { scanf("%d", &r); if (r==25) { t[0]++; } else if (r==50) { if (t[0]>0) { t[0]--; t[1]++; } else { puts("NO"); return 0; } } else { if (t[1]>0) { t[1]--; if (t[0]>0) { t[0]--; } else { puts("NO"); return 0; } } else if (t[0]>=3) { t[0]-=3; } else { puts("NO"); return 0; } } } puts("YES"); return 0; } /*****************************************************************************/
UVa 11284
non-classic TSP problem, Floyd for shortest path and DP are used here
matrix g is used to maintain shortest path of all point pairs
matrix g2 is used to maintain actually cost, because we don't need to traverse all points
state:
dp[i][j] - maximum money saved when point i is visited, j is the bitmask, all have the same
meaning with tradition TSP problem except we are maximizing how much money saved
transition:
dp[i][j]=max(dp[i][j], dp[i][j|(1<<k)], dp[k][j|(1<<k)]-dist2[i][k]+u[k-1])
because now we have 2 choices, to buy or not to buy at store k
matrix g is used to maintain shortest path of all point pairs
matrix g2 is used to maintain actually cost, because we don't need to traverse all points
state:
dp[i][j] - maximum money saved when point i is visited, j is the bitmask, all have the same
meaning with tradition TSP problem except we are maximizing how much money saved
transition:
dp[i][j]=max(dp[i][j], dp[i][j|(1<<k)], dp[k][j|(1<<k)]-dist2[i][k]+u[k-1])
because now we have 2 choices, to buy or not to buy at store k
/* UVas */
/*****************************************************************************/
int t, n, m, p;
int main(void) {
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
n++;
double g[n][n];
for (int i=0; i<n; i++)
fill(g[i], g[i]+n, (double)INT_MAX);
for (int i=0; i<m; i++) {
int a, b;
double c;
scanf("%d %d %lf", &a, &b, &c);
g[a][b]=g[b][a]=min(g[a][b], c);
}
scanf("%d", &p);
int s[p];
double u[p];
double g2[p+1][p+1];
double d[p+1][1<<(p+1)];
for (int i=0; i<p; i++)
scanf("%d %lf", &s[i], &u[i]);
/* Floyd */
for (int k=0; k<n; k++)
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
g[i][j]=min(g[i][j], g[i][k]+g[k][j]);
/**/
for (int i=0; i<p; i++)
g2[0][i+1]=g2[i+1][0]=g[0][s[i]];
for (int i=1; i<=p; i++)
for (int j=1; j<=p; j++)
g2[i][j]=g[s[i-1]][s[j-1]];
for (int i=0; i<p+1; i++) {
fill(d[i], d[i]+(1<<(p+1)), (double)INT_MIN);
d[i][(1<<(p+1))-1]=-g2[i][0];
}
/* TSP */
for (int mask=(1<<(p+1))-1; mask>=0; mask--)
for (int i=0; i<p+1; i++)
if (mask&(1<<i))
for (int j=0; j<p+1; j++)
if (!(mask&(1<<j)))
d[i][mask]=max(d[i][mask],
max(d[i][mask|(1<<j)],
d[j][mask|(1<<j)]-g2[i][j]+u[j-1]));
/**/
(abs(d[0][1])>1e-9)&&(d[0][1]>0)?
printf("Daniel can save $%.2lf\n", d[0][1]):
printf("Don't leave the house\n");
}
}
/*****************************************************************************/
UVa 10496
classic TSP problem again, the same with UVa 216
/* UVas */
/*****************************************************************************/
int t, r, c, n;
int xs, ys;
int main(void) {
scanf("%d", &t);
while (t--) {
scanf("%d %d", &r, &c);
scanf("%d %d", &xs, &ys);
scanf("%d", &n);
n++;
int x[n], y[n];
int g[n][n];
int d[n][1<<n];
int p[n][1<<n];
x[0]=xs, y[0]=ys;
for (int i=1; i<n; i++)
scanf("%d %d", &x[i], &y[i]);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
g[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j]);
for (int i=0; i<n; i++) {
fill(d[i], d[i]+(1<<n), INT_MAX);
d[i][(1<<n)-1]=0;
}
memset(p, 0, sizeof(p));
for (int mask=(1<<n)-2; mask>=0; mask--)
for (int i=0; i<n; i++)
if (mask&(1<<i))
for (int j=0; j<n; j++)
if (!(mask&(1<<j)))
if (d[i][mask]>d[j][mask|(1<<j)]+g[i][j]) {
d[i][mask]=d[j][mask|(1<<j)]+g[i][j];
p[i][mask]=j;
}
int s=0;
int mask=1;
while (mask!=(1<<n)-1) {
int j=p[s][mask];
mask|=(1<<j);
s=j;
}
printf("The shortest path has length %d\n", d[0][1]+g[0][s]);
}
}
/*****************************************************************************/
UVa 216
classic TSP problem, the maximum point number is 8, so it can be solved by dynamic programming efficiently, there is also a requirement to record the path with minimum cost, hence...classic solution to the classic problem...
state:
dp[i][j] - minimum cost when point i is visited, with j points visited
j is a bitmask indicating how many points we have visited, so the initial state should be
dp[k][111...111], for all point k, which means we have visited all the points and end at k
the next NODES in DAG of initial state should be dp[k][111...111&(~(1<<l))], for all points k,
which means we now end at k, but there is still another point being not visited
transition:
dp[i][j]=min(dp[i][j], dp[k][j|k]+dist[i][k]+SOME_CONST_COST
for all k that are not visited
state:
dp[i][j] - minimum cost when point i is visited, with j points visited
j is a bitmask indicating how many points we have visited, so the initial state should be
dp[k][111...111], for all point k, which means we have visited all the points and end at k
the next NODES in DAG of initial state should be dp[k][111...111&(~(1<<l))], for all points k,
which means we now end at k, but there is still another point being not visited
transition:
dp[i][j]=min(dp[i][j], dp[k][j|k]+dist[i][k]+SOME_CONST_COST
for all k that are not visited
/* UVas */
/*****************************************************************************/
const int N=8;
const double O=16.0;
int n, t=1;
int x[N], y[N];
int p[N][1<<N];
double g[N][N];
double d[N][1<<N];
int main(void) {
while (scanf("%d", &n)>0&&n) {
for (int i=0; i<n; i++)
scanf("%d %d", &x[i], &y[i]);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
g[i][j]=hypot(x[i]-x[j], y[i]-y[j]);
for (int i=0; i<n; i++) {
fill(d[i], d[i]+(1<<n), (double)INT_MAX);
fill(p[i], p[i]+(1<<n), 0);
}
for (int i=0; i<n; i++)
d[i][(1<<n)-1]=0.0;
for (int mask=(1<<n)-1; mask>=0; mask--)
for (int i=0; i<n; i++)
if (mask&(1<<i))
for (int j=0; j<n; j++)
if (!(mask&(1<<j)))
if (d[i][mask]>d[j][mask|(1<<j)]+g[i][j]+O) {
d[i][mask]=d[j][mask|(1<<j)]+g[i][j]+O;
p[i][mask]=j;
}
int s=0;
for (int i=1; i<n; i++)
if (d[i][1<<i]<d[s][1<<s])
s=i;
printf("**********************************************************\n");
printf("Network #%d\n", t++);
int mask=1<<s;
int e=s;
while (mask!=(1<<n)-1) {
int j=p[s][mask];
printf("Cable requirement to connect ");
printf("(%d,%d) to (%d,%d) is %.2lf feet.\n", x[s], y[s], x[j], y[j], g[s][j]+O);
mask|=(1<<j);
s=j;
}
printf("Number of feet of cable required is %.2lf.\n", d[e][1<<e]);
}
}
/*****************************************************************************/
UVa 11658
0-1 knapsack problem...
/* UVas */
/*****************************************************************************/
#define N 101
#define M 10001
int n, idx, x, y;
int h[N];
int d[M];
int main(void) {
while (scanf("%d %d", &n, &idx)>0&&n) {
for (int i=1; i<=n; i++) {
scanf("%d.%d", &x, &y), h[i]=x*100+y;
}
int me=h[idx];
memset(d, 0, sizeof(d));
d[me]=1;
for (int i=1; i<=n; i++) {
if (i==idx) continue;
for (int j=M-1; j>=h[i]; j--)
d[j]|=d[j-h[i]];
}
double r=0;
for (int i=5001; i<M; i++)
if (d[i])
r=max(r, (me/(double)i)*100);
printf("%.2lf\n", r);
}
}
/*****************************************************************************/
UVa 11341
based on classic 0-1 knapsack problem, the DAG is extended to 3-dimension, it needs an iteration on the giving out 2-dimension table. When doing, make sure that current table element is above 5. Also, DP matrix need to be initialized to -1 for reaching check...
/* UVas */
/*****************************************************************************/
#define N 11
#define M 101
int t, n, m;
int g[N][M];
int d[N][M];
int main(void) {
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
scanf("%d", &g[i][j]);
memset(d, -1, sizeof(d));
d[0][0]=0;
for (int i=1; i<=n; i++)
for (int j=m; j&&g[i][j]>=5; j--)
for (int k=m; k>=j; k--)
if (d[i-1][k-j]!=-1)
d[i][k]=max(d[i][k], d[i-1][k-j]+g[i][j]);
if (d[n][m]==-1)
printf("Peter, you shouldn't have played billiard that much.\n");
else
printf("Maximal possible average mark - %.2lf.\n", (double)(d[n][m]+1e-9)/n);
}
}
/*****************************************************************************/
UVa 10819
0-1 knapsack problem with a tricky modification, which is the if condition in dp iteration
j==p[i]||(j>p[i]&&d[j-p[i]])
this will generate a scattered dp table, not like the original continuous one.
j==p[i]||(j>p[i]&&d[j-p[i]])
this will generate a scattered dp table, not like the original continuous one.
/* UVas */
/*****************************************************************************/
#define N 100
#define M 10201
int m, n;
int p[N];
int f[N];
int d[M];
int main(void) {
while ( scanf("%d %d", &m, &n)>0) {
for (int i=0; i<n; i++)
scanf("%d %d", &p[i], &f[i]);
memset(d, 0, sizeof(d));
for (int i=0; i<n; i++)
for (int j=M-1; j>=p[i]; j--)
if (j==p[i]||(j>p[i]&&d[j-p[i]]))
d[j]=max(d[j], d[j-p[i]]+f[i]);
int r=0;
for (int i=0; i<M; i++)
if ((i>2000&&i<=m+200)||i<=m)
r=max(r, d[i]);
printf("%d\n", r);
}
}
/*****************************************************************************/
UVa 10664
an easy 0-1 knapsack problem
strtok and gets are used to parse input...
strtok and gets are used to parse input...
/* UVas */
/*****************************************************************************/
#define N 21
#define S 101
#define BUF 512
int m;
int l[N];
int d[S];
char str[BUF];
int main(void) {
scanf("%d", &m);
gets(str);
while (m--) {
gets(str);
int i, s=0, idx=0;
for (char *ptr=strtok(str, " "); ptr; ptr=strtok(0, " ")) {
i=atoi(ptr), l[idx++]=i, s+=i;
}
if (s%2) {
printf("NO\n");
continue;
}
s/=2;
memset(d, 0, sizeof(d));
d[0]=1;
for (int i=0; i<idx; i++)
for (int j=S-1; j>=l[i]; j--)
d[j]|=d[j-l[i]];
d[s]?printf("YES\n"):printf("NO\n");
}
}
/*****************************************************************************/
UVa 10616
state:
dp[i][j][k] - how many ways to select j numbers from i numbers, and with remainder k when the sum of those j numbers divides d
transition:
dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][K], K equals the remainder before we select number j
this dp transition looks just like the one used to generate combination table:
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
which also can generate the famous pascal's triangle...
dp[i][j][k] - how many ways to select j numbers from i numbers, and with remainder k when the sum of those j numbers divides d
transition:
dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][K], K equals the remainder before we select number j
this dp transition looks just like the one used to generate combination table:
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
which also can generate the famous pascal's triangle...
/* UVas */
/*****************************************************************************/
#define N 201
#define M 21
int n, q, d, m, t=1;
int p[N];
unsigned long long D[N][M][M];
int main(void) {
while (scanf("%d %d\n", &n, &q)>0&&n&&q) {
for (int i=1; i<=n; i++)
scanf("%d", &p[i]);
printf("SET %d:\n", t++);
for (int i=1; i<=q; i++) {
scanf("%d %d", &d, &m);
printf("QUERY %d: ", i);
memset(D, 0, sizeof(D));
for (int i=0; i<=n; i++)
D[i][0][0]=1;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
for (int k=0; k<d; k++) {
int r=(k-p[i]%d)%d;
D[i][j][k]=D[i-1][j][k]+D[i-1][j-1][r>=0?r:r+d];
}
printf("%lld\n", D[n][m][0]);
}
}
}
/*****************************************************************************/
UVa 1213
easy 0-1 knapsack problem
state:
dp[i][j] - how many ways to form integer i using j primes
transition:
dp[i][j]+=dp[i-p[k]][j-1], for all j from 1 to 14
a trick to generate primes table is also used here
state:
dp[i][j] - how many ways to form integer i using j primes
transition:
dp[i][j]+=dp[i-p[k]][j-1], for all j from 1 to 14
a trick to generate primes table is also used here
/* UVas */
/*****************************************************************************/
#define N 1121
#define K 15
#define P 187
int n, k;
int d[N][K]={};
int m[N];
int p[P];
int main(void) {
p[0]=2;
for (int i=2; i*i<N; i++)
for (int j=i+i; j<N; j+=i)
m[j]=1;
for (int i=2, j=0; i<N; i++)
if (!m[i])
p[j++]=i;
d[0][0]=1;
for (int i=0; i<P; i++)
for (int j=N-1; j>=p[i]; j--)
for(int l=1; l<K; l++)
d[j][l]+=d[j-p[i]][l-1];
while (scanf("%d %d", &n, &k)>0&&n&&k) {
printf("%d\n", d[n][k]);
}
}
/*****************************************************************************/
UVa 11368
according to this solution...
Solution
and this tutorial on Binary Indexed Tree...
Tutorial
binary indexed tree in this problem is used to get V
state:
dp[i] - minimum dolls sequence at position i, the same with LIS's state
transition:
dp[i]=max(dp[i], V+1)
V is max(dp[k]), for all k<i
Solution
and this tutorial on Binary Indexed Tree...
Tutorial
binary indexed tree in this problem is used to get V
state:
dp[i] - minimum dolls sequence at position i, the same with LIS's state
transition:
dp[i]=max(dp[i], V+1)
V is max(dp[k]), for all k<i
/* UVas */
/*****************************************************************************/
struct doll {
int d[2];
inline bool operator<(const doll &o) const {
if (d[0]==o.d[0])
return d[1]>o.d[1];
return d[0]<o.d[0];
}
} D[20000];
int t, m;
int read(int i, int *a) {
int r=0;
while (i) {
r=max(r, a[i]);
i-=i&(-i);
}
return r;
}
void updt(int i, int *a, int l, int arg) {
while (i<=l) {
a[i]=max(a[i], arg);
i+=i&(-i);
}
}
int main(void) {
scanf("%d", &t);
while (t--) {
scanf("%d", &m);
for (int i=0; i<m; i++)
scanf("%d %d", &D[i].d[0], &D[i].d[1]);
sort(D, D+m);
int d[20000]={};
int h[2][10001]={};
int r=0;
for (int i=0; i<m; i++) {
for (int j=0; j<2; j++) {
int f=read(10001-D[i].d[j], h[j]);
d[i]=max(d[i], f+1);
updt(10001-D[i].d[j], h[j], 10001, d[i]);
}
r=max(r, d[i]);
}
printf("%d\n", r);
}
}
/*****************************************************************************/
UVa 1196
an easy DP problem
state:
dp[i][j] - maximum height when block(s) of l=i and m=j is(are) on top
transition:
dp[i][j]+=max(dp[i-1][j], dp[i][j-1])
each step we have two choices...
state:
dp[i][j] - maximum height when block(s) of l=i and m=j is(are) on top
transition:
dp[i][j]+=max(dp[i-1][j], dp[i][j-1])
each step we have two choices...
/* UVas */
/*****************************************************************************/
struct block {
int l, m;
} b[10000];
int n;
int d[101][101];
int main(void) {
while (scanf("%d", &n)>0&&n) {
memset(d, 0, sizeof(d));
for (int i=0; i<n; i++) {
scanf("%d %d", &b[i].l, &b[i].m);
d[b[i].l][b[i].m]++;
}
int r=0;
for (int i=1; i<=100; i++)
for (int j=1; j<=100; j++) {
d[i][j]+=max(d[i-1][j], d[i][j-1]);
r=max(r, d[i][j]);
}
printf("%d\n", r);
}
printf("*\n");
}
/*****************************************************************************/
UVa 437
key point here for LIS is how to sort these blocks, and for each block, there will be 6 arrangements
the override operator is just a guess...
the override operator is just a guess...
/* UVas */
/*****************************************************************************/
struct block {
int x, y, h;
inline bool operator<(const block &o) const {
if (x==o.x)
return y<o.y;
return x<o.x;
}
} b[180];
int n, ce=1;
int d[180];
int main(void) {
while (scanf("%d", &n)>0&&n) {
for (int i=0; i<n; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
b[i*6].x=x, b[i*6].y=y, b[i*6].h=z;
b[i*6+1].x=x, b[i*6+1].y=z, b[i*6+1].h=y;
b[i*6+2].x=y, b[i*6+2].y=x, b[i*6+2].h=z;
b[i*6+3].x=y, b[i*6+3].y=z, b[i*6+3].h=x;
b[i*6+4].x=z, b[i*6+4].y=x, b[i*6+4].h=y;
b[i*6+5].x=z, b[i*6+5].y=y, b[i*6+5].h=x;
}
sort(b, b+6*n);
int r=0;
d[0]=b[0].h;
for (int i=1; i<6*n; i++) {
d[i]=b[i].h;
for (int j=0; j<i; j++)
if (b[j].x<b[i].x&&b[j].y<b[i].y&&d[j]+b[i].h>d[i])
d[i]=d[j]+b[i].h;
r=max(r, d[i]);
}
printf("Case %d: maximum height = %d\n", ce++, r);
}
}
/*****************************************************************************/
UVa 11951
first the 2-D array is row-major compressed to 1-D, which means each time more row's columns are iterated at the same time, pointer h is used to calculate area
j-i+1 is the total rows being iterated now
k-h+1 is the maximum column number that satisfy the limit
j-i+1 is the total rows being iterated now
k-h+1 is the maximum column number that satisfy the limit
/* UVas */
/*****************************************************************************/
#define ll long long
int t, N, M, ce=1;
ll K;
ll mat2[100][100];
ll mat1[100];
int main(void) {
scanf("%d", &t);
while (t--) {
scanf("%d %d %lld", &N, &M, &K);
for (int i=0; i<N; i++)
for (int j=0; j<M; j++)
scanf("%lld", &mat2[i][j]);
ll r0=0, r1=0;
for (int i=0; i<N; i++) {
memset(mat1, 0, sizeof(mat1));
for (int j=i; j<N; j++) {
for (int k=0; k<M; k++)
mat1[k]+=mat2[j][k];
int h=0;
ll c=0;
for (int k=0; k<M; k++) {
c+=mat1[k];
while (c>K)
c-=mat1[h++];
ll a=(j-i+1)*(k-h+1);
if (a>r0) {
r0=a;
r1=c;
} else if (a==r0) {
r1=min(r1, c);
}
}
}
}
printf("Case #%d: %lld %lld\n", ce++, r0, r1);
}
}
/*****************************************************************************/
UVa 983
after looking into other's solution, I found again the array need compression
origin:
1 2 2 1
1 0 2 2
0 2 3 3
1 2 1 3
after 1st compression: (column)
1 3 5 6
1 1 3 5
0 2 5 8
1 3 4 7
after 2nd compression: (row)
1 3 5 6
2 4 8 11
2 6 13 19
3 9 17 26
origin:
1 2 2 1
1 0 2 2
0 2 3 3
1 2 1 3
after 1st compression: (column)
1 3 5 6
1 1 3 5
0 2 5 8
1 3 4 7
after 2nd compression: (row)
1 3 5 6
2 4 8 11
2 6 13 19
3 9 17 26
now mat[i][j] represents the sum of elements from mat[0][0] to mat[i][j]
hence to calculate the sum from mat[i0][j0] to mat[i1][j1]
we need to exclude some rows (mat[0][0]-mat[i0-1][j1]), some columns(mat[0][0]-mat[i1][j0-1])
of course, if we exclude rows and columns at the same time, mat[i0][j0] is excluded twice.
so add back it...
/* UVas */
/*****************************************************************************/
#define ull unsigned long long
int n, m, ce=0;
int mat[1000][1000];
ull calc(int i0, int j0, int i1, int j1) {
int r=mat[i1][j1];
if(j0>=1) r-=mat[i1][j0-1];
if(i0>=1) r-=mat[i0-1][j1];
if(i0>=1&&j0>=1) r+=mat[i0-1][j0-1];
return r;
}
int main(void) {
while (scanf("%d %d", &n, &m)>0) {
if (ce) printf("\n");
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
scanf("%d", &mat[i][j]);
for (int i=0; i<n; i++)
for (int j=1; j<n; j++)
mat[i][j]+=mat[i][j-1];
for (int i=0; i<n; i++)
for (int j=1; j<n; j++)
mat[j][i]+=mat[j-1][i];
ull r=0, c=0;
for (int i=0; i<n-m+1; i++)
for (int j=0; j<n-m+1; j++) {
c=calc(i, j, i+m-1, j+m-1);
r+=c;
printf("%llu\n", c);
}
printf("%llu\n", r);
ce++;
}
}
/*****************************************************************************/
UVa 10755
kadane's algorithm on 3-dimension array
origin array is compressed 2 times to 1-dimension
origin array is compressed 2 times to 1-dimension
/* UVas */
/*****************************************************************************/
int t, a, b, c;
long long d3[21][21][21];
long long d2[21][21];
long long d1[21];
int main(void) {
cin>>t;
while (t--) {
cin>>a>>b>>c;
for (int i=0; i<a; i++)
for (int j=0; j<b; j++)
for (int k=0; k<c; k++) cin>>d3[i][j][k];
long long r=INT_MIN;
for (int i=0; i<a; i++) { // first compression
memset(d2, 0, sizeof(d2));
for (int ii=i; ii<a; ii++) {
for (int j=0; j<b; j++)
for (int k=0; k<c; k++) d2[j][k]+=d3[ii][j][k];
for (int i=0; i<b; i++) { // second compression
memset(d1, 0, sizeof(d1));
for (int j=i; j<b; j++) {
for (int k=0; k<c; k++) d1[k]+=d2[j][k];
long long n=d1[0];
r=max(r, n);
for (int k=1; k<c; k++) {
n=max(n, 0LL);
n+=d1[k];
r=max(r, n);
}
}
}
}
}
cout<<r<<endl;
if (t) cout<<endl;
}
}
/*****************************************************************************/
Topcoder SRM 589 DIV2 EASY
/* Topcoder SRM */
/*****************************************************************************/
int GooseTattarrattatDiv2::getmin(string S) {
int c[26];
int n=S.size();
memset(c, 0, sizeof(c));
for (int i=0; i<n; i++) {
c[S[i]-'a']++;
}
int r=INT_MAX;
for (int i=0; i<26; i++) {
if (!c[i]) {
continue;
}
r=min(r, n-c[i]);
}
return r;
}
/*****************************************************************************/
UVa 787
this is a straight O(n**2) solution, which relies on java's BitInteger...
/* UVa */
/*****************************************************************************/
public class Main {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
ArrayList<Integer> n=new ArrayList<Integer>();
while (sc.hasNext()) {
int c=sc.nextInt();
if (c!=-999999) {
n.add(c);
continue;
}
BigInteger m=BigInteger.valueOf(c);
BigInteger p=BigInteger.valueOf(0);
for(int i=0; i<n.size(); i++) {
p=BigInteger.valueOf(1);
for(int j=i; j<n.size(); j++) {
p=p.multiply(BigInteger.valueOf(n.get(j)));
if(p.compareTo(m)==1) {
m=p;
}
}
}
System.out.println(m.toString());
n.clear();
}
}
}
/*****************************************************************************/
Topcoder SRM 590 DIV1 EASY
if the number of pawns of begin and target are not equal, return with impossible
it has 3 conditions that begin can't turn to target:
1 pawns' order is not the same
2 pawn R in target is shifted left to the position in begin
3 pawn L in target is shifted right to the position in begin
it has 3 conditions that begin can't turn to target:
1 pawns' order is not the same
2 pawn R in target is shifted left to the position in begin
3 pawn L in target is shifted right to the position in begin
/* Topcoder SRM */
/*****************************************************************************/
vector<int> filt(string s) {
vector<int> r;
for (int i=0; i<sz(s); i++) {
if (s[i]!='.') {
r.pb(i);
}
}
return r;
}
string FoxAndChess::ableToMove(string begin, string target) {
vector<int> b=filt(begin), t=filt(target);
if (sz(b)!=sz(t)) {
return "Impossible";
}
for (int i=0; i<sz(b); i++) {
if (begin[b[i]]!=target[t[i]]||
begin[b[i]]=='R'&&t[i]<b[i]||
begin[b[i]]=='L'&&t[i]>b[i]) {
return "Impossible";
}
}
return "Possible";
}
/*****************************************************************************/
Topcoder SRM 590 DIV2 HARD
took me so much time on understanding this DP approach...
Solution
Solution
/* Topcoder SRM */
/*****************************************************************************/
const int mod=1e9+7;
long long solve(string c) {
vector<int> x;
for (int i=0; i<sz(c); i++) {
if (c[i]!='.') {
x.pb(i);
}
}
int t=sz(x), n=sz(c);
int d[t+1][n+1];
for (int i=t; i>=0; i--) {
for (int p=n; p>=0; p--) {
long &r=d[i][p];
if (i==t) {
r=1;
} else {
int hi=n-(t-i), lo=p;
c[x[i]]=='D'?lo=max(p, x[i]):hi=min(hi, x[i]);
r=0;
for (int j=lo; j<=hi; j++) {
r+=d[i+1][j+1];
}
r%=mod;
}
}
}
return d[0][0];
}
int FoxAndShogi::differentOutcomes(vector <string> board) {
int n=sz(board);
long long r=1;
for (int i=0; i<n; i++) {
string c="";
for (int j=0; j<n; j++) {
c+=board[j][i];
}
r*=solve(c);
r%=mod;
}
return r;
}
/*****************************************************************************/
Topcoder SRM 590 DIV2 MEDIUM
graph problem, BFS need to be modified that it should keep records of current tokens'
border points, for maximum score, we only need to check tokens whose border number is
0 and 1, for 0, just add all tokens, for 1, do a n**2 iteration and add those pairs whose
border number equals 1 and the border point is the same
border points, for maximum score, we only need to check tokens whose border number is
0 and 1, for 0, just add all tokens, for 1, do a n**2 iteration and add those pairs whose
border number equals 1 and the border point is the same
/* Topcoder SRM */
/*****************************************************************************/
struct point {
int x, y;
inline bool operator==(const point &o) const {
return x==o.x&&y==o.y;
}
};
struct token {
int n;
vector<point> p;
inline bool operator==(const token &o) const {
return sz(p)==1&&sz(o.p)==1&&p[0]==o.p[0];
}
};
int n;
int d[4][2]={{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int v[20][20];
int vb[20][20];
vector<token> t;
void bfs(vector<string> &board, int i, int j) {
token tk;
tk.n=1;
point s={i, j};
queue<point> q;
q.push(s);
v[i][j]=1;
while (!q.empty()) {
point c=q.front(); q.pop();
for (int i=0; i<4; i++) {
int nx=c.x+d[i][0], ny=c.y+d[i][1];
if (nx<0||nx>=n||ny<0||ny>=n) {
continue;
}
if (v[nx][ny]||board[nx][ny]=='x') { continue; }
if (vb[nx][ny]) {
continue;
}
if (board[nx][ny]=='.') {
point adj={nx, ny};
tk.p.pb(adj);
vb[nx][ny]=1;
continue;
}
tk.n++;
v[nx][ny]=1;
point nc={nx, ny};
q.push(nc);
}
}
t.pb(tk);
}
int FoxAndGo::maxKill(vector <string> board) {
n=sz(board);
t.clear();
memset(v, 0, sizeof(v));
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (v[i][j]||board[i][j]!='o') {
continue;
}
memset(vb, 0, sizeof(vb));
bfs(board, i, j);
}
}
int r=0;
for (int i=0; i<sz(t); i++) {
if (sz(t[i].p)==0) {
r+=t[i].n;
}
}
int rr=0;
for (int i=0; i<sz(t); i++) {
if (sz(t[i].p)!=1) {
continue;
}
int cr=t[i].n;
for (int j=i+1; j<sz(t); j++) {
if (t[i]==t[j]) {
cr+=t[j].n;
}
}
rr=max(rr, cr);
}
return r+rr;
}
/*****************************************************************************/
Topcoder SRM 590 DIV2 EASY
be careful with the boundary...
/* Topcoder SRM */
/*****************************************************************************/
string FoxAndGomoku::win(vector <string> board) {
for (int i=0; i<sz(board); i++) {
for (int j=0; j<sz(board[0]); j++) {
if (board[i][j]=='.') {
continue;
}
int k;
for (k=1; k<5&&i+k>=0&&i+k<sz(board)&&board[i+k][j]=='o'; k++) { }
if (k==5) { return "found"; }
for (k=1; k<5&&j+k>=0&&j+k<sz(board[0])&&board[i][j+k]=='o'; k++) { }
if (k==5) { return "found"; }
for (k=1; k<5&&i+k>=0&&i+k<sz(board)&&j+k>=0&&j+k<sz(board[0])&&board[i+k][j+k]=='o'; k++) { }
if (k==5) { return "found"; }
for (k=1; k<5&&i+k>=0&&i+k<sz(board)&&j-k>=0&&j-k<sz(board[0])&&board[i+k][j-k]=='o'; k++) { }
if (k==5) { return "found"; }
}
}
return "not found";
}
/*****************************************************************************/
UVa 10474
so easy...
/* UVas */
/*****************************************************************************/
int n, q, t, c=1;
int main(void) {
while (cin>>n>>q&&n&&q) {
int m[n];
for (int i=0; i<n; i++) {
cin>>m[i];
}
cout<<"CASE# "<<c<<":"<<endl;
for (int i=0; i<q; i++) {
cin>>t;
int r=0, f=0;
for (int j=0; j<n; j++) {
if (m[j]<t) {
r++;
}
if (m[j]==t) {
f=1;
}
}
f?cout<<t<<" found at "<<r+1:cout<<t<<" not found";
cout<<endl;
}
c++;
}
return 0;
}
/*****************************************************************************/
UVa 10611
easy DC problem can be solved by binary search again...
/* UVas */
/*****************************************************************************/
int n, q, t;
vector<int> h;
int main(void) {
while (cin>>n) {
h.clear();
for (int i=0; i<n; i++) {
scanf("%d", &t);
h.pb(t);
}
cin>>q;
for (int i=0; i<q; i++) {
scanf("%d", &t);
vector<int>::iterator lo=lower_bound(all(h), t);
vector<int>::iterator hi=upper_bound(all(h), t);
int a=lo-h.begin()-1;
int b=hi-h.begin();
(a<n&&a>=0)?printf("%d", h[a]):printf("X");
printf(" ");
(b<n&&n>=0)?printf("%d", h[b]):printf("X");
printf("\n");
}
}
return 0;
}
/*****************************************************************************/
UVa 10341
another simple DC problem be solved by bisection method
notice to the 3 conditions when current x is smaller than desired x
notice to the 3 conditions when current x is smaller than desired x
/* UVas */
/*****************************************************************************/
int p, q, r, s, t, u;
double calc(double mid) {
return p*exp(-mid)+q*sin(mid)+r*cos(mid)+s*tan(mid)+t*mid*mid+u;
}
int main(void) {
while (cin>>p>>q>>r>>s>>t>>u) {
double l=0.0, h=1.0, mid, x, y;
while (h-l>0.000000001) {
mid=(l+h)/2;
x=calc(mid);
y=calc(h);
if((y<0&x>0)||(y>=0&&x>y)||(y<=0&&y>x)) {
l=mid;
} else {
h=mid;
}
}
abs(x)<=0.0001?printf("%.4f\n", mid):printf("No solution\n");
}
return 0;
}
/*****************************************************************************/
UVa 957
a simple DC problem, binary search on each node and find the maximum one
/* UVas */
/*****************************************************************************/
int y, p, t;
int r, s, e;
vector<int> year;
int main(void) {
while (cin>>y) {
cin>>p;
year.clear();
for (int i=0; i<p; i++) {
cin>>t;
year.pb(t);
}
r=0;
for (int i=0; i<p; i++) {
int f=year[i]+y-1;
vector<int>::iterator it=upper_bound(year.begin()+i, year.end(), f);
int id=it-year.begin();
if ((id-i)>r) {
r=id-i;
s=year[i];
e=year[id-1];
}
}
cout<<r<<" "<<s<<" "<<e<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 714
D&C problem, do a binary search on range [0, sum of pages]
make a guess on the maximum pages assigned to one scriber each time
as for calculating the real maximum pages, j<k-1 ensures there are enough
scribers left, and if r+b[i]>mid, we should split here, or if i<k-j-1, means books
left are now enough, so have to assigned 1 book to 1 scriber for left books
make a guess on the maximum pages assigned to one scriber each time
as for calculating the real maximum pages, j<k-1 ensures there are enough
scribers left, and if r+b[i]>mid, we should split here, or if i<k-j-1, means books
left are now enough, so have to assigned 1 book to 1 scriber for left books
/* UVas */
/*****************************************************************************/
int n, m, k;
int v[500];
long long b[500];
long long bin(long long mid) {
long long r=0, MAX=0;
for (int i=m-1, j=0; i>=0; i--) {
if (j<k-1&&(i<k-j-1||r+b[i]>mid)) {
MAX=max(MAX, r);
r=b[i];
v[i]=1;
j++;
}
else {
r+=b[i];
}
}
return max(MAX, r);
}
int main(void) {
cin>>n;
while (n--) {
cin>>m>>k;
long long l=0, h=0, mid, r;
for (int i=0; i<m; i++) {
cin>>b[i];
h+=b[i];
}
while (l<h) {
mid=(l+h)>>1;
r=bin(mid);
r>mid?l=mid+1:h=mid;
}
memset(v, 0, sizeof(v));
bin(l);
for (int i=0; i<m; i++) {
cout<<(i==0?"":" ")<<b[i]<<(v[i]?" /":"")<<(i==m-1?"\n":"");
}
}
return 0;
}
/*****************************************************************************/
UVa 679
there is an interesting regular pattern here
for depth 1, the left-right cycle is two balls
for depth 2, the cycle is 4 balls
...
for depth k, the cycle is 1<<k balls
and the branch condition, i%2?goleft:goright won't change forever
for depth 1, the left-right cycle is two balls
for depth 2, the cycle is 4 balls
...
for depth k, the cycle is 1<<k balls
and the branch condition, i%2?goleft:goright won't change forever
/* UVas */
/*****************************************************************************/
int n, D, I;
int main(void) {
cin>>n;
while(n--) {
cin>>D>>I;
int k=1;
for (int i=1; i<D; i++) {
if (I%2) {
I=(I+1)/2;
k*=2;
} else {
I/=2;
k=k*2+1;
}
}
cout<<k<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 10911
tree-structure dp plus bitmask technics
state:
dp[i] - minimum dist when we have formed groups indicated by i
so when i==(1<<2*n)-1, all groups will be paired
transition:
dp[i]=min(d[x][y]+dp[i|(1<<x)|(1<<y)]
for all next states of i (set two bits to 1 each time), thus x, y are next pair, and d[x][y]
is their distance
state:
dp[i] - minimum dist when we have formed groups indicated by i
so when i==(1<<2*n)-1, all groups will be paired
transition:
dp[i]=min(d[x][y]+dp[i|(1<<x)|(1<<y)]
for all next states of i (set two bits to 1 each time), thus x, y are next pair, and d[x][y]
is their distance
/* UVas */
/*****************************************************************************/
int n, c=1;
int s[16][2];
double d[16][16];
double dp[1<<16];
string t;
double dfs(int s) {
double &r=dp[s];
if (r>-1) {
return r;
} else if (s==(1<<2*n)-1) {
r=0;
return r;
} else {
r=1e9;
for (int i=0; i<2*n; i++) {
if (!(s&(1<<i))) {
for (int j=i+1; j<2*n; j++) {
if (!(s&(1<<j))) {
r=min(r, d[i][j]+dfs(s|(1<<i)|(1<<j)));
}
}
break;
}
}
return r;
}
}
int main(void) {
while (cin>>n&&n) {
for (int i=0; i<2*n; i++) {
cin>>t>>s[i][0]>>s[i][1];
}
for (int i=0; i<2*n; i++) {
for (int j=0; j<2*n; j++) {
int x0=s[i][0], y0=s[i][1];
int x1=s[j][0], y1=s[j][1];
d[i][j]=sqrt((double)(x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
}
}
memset(dp, -1, sizeof(dp));
printf("Case %d: %.2lf\n", c++, dfs(0));
}
return 0;
}
/*****************************************************************************/
UVa 10908
seems this problem has nothing to do with dp, but keeping record of solved pair is better
state:
d[i][j] - max square length with i, j as center
transition:
NONE
state:
d[i][j] - max square length with i, j as center
transition:
NONE
/* UVas */
/*****************************************************************************/
int t, m, n, q;
int p[20][2];
int d[100][100];
char s[100][100];
int calc(int x, int y) {
int &r=d[x][y];
if (r!=-1) {
return r;
} else {
r=0;
for (int k=0; x-k>=0&&x+k<m&&y-k>=0&&y+k<n; k++) {
for (int i=x-k; i<=x+k; i++) {
for (int j=y-k; j<=y+k; j++) {
if (s[i][j]!=s[x][y]) {
return 2*(k-1)+1;
}
}
}
r=max(r, 2*k+1);
}
}
return r;
}
int main(void) {
cin>>t;
while (t--) {
cin>>m>>n>>q;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
cin>>s[i][j];
}
}
for (int i=0; i<q; i++) {
cin>>p[i][0]>>p[i][1];
}
memset(d, -1, sizeof(d));
cout<<m<<" "<<n<<" "<<q<<endl;
for (int i=0; i<q; i++) {
cout<<calc(p[i][0], p[i][1])<<endl;
}
}
return 0;
}
/*****************************************************************************/
UVa 10651
another tree structure dp problem, while using bitmask representing state
state:
dp[i] - minimum pebbles left when reaching state i
transition:
dp[i]=min(dp[k]), for all k is pre state of i
leaf nodes are those states can't move any more
state:
dp[i] - minimum pebbles left when reaching state i
transition:
dp[i]=min(dp[k]), for all k is pre state of i
leaf nodes are those states can't move any more
/* UVas */
/*****************************************************************************/
int n, b;
int d[1<<12];
string t;
int dfs(int b) {
int &r=d[b];
if (r!=-1) {
return r;
} else {
r=INT_MAX;
for (int i=0; i<12; i++) {
if ((1<<i)&b) {
if (((1<<(i-1))&b)&&!((1<<(i-2))&b)&&i>1) {
int nb=b&~(1<<i);
nb&=~(1<<(i-1));
nb|=1<<(i-2);
r=min(r, dfs(nb));
}
if (((1<<(i+1))&b)&&!((1<<(i+2))&b)&&i<10) {
int nb=b&~(1<<i);
nb&=~(1<<(i+1));
nb|=1<<(i+2);
r=min(r, dfs(nb));
}
}
}
int re=0;
for (int i=0; i<12; i++) {
if ((1<<i)&b) {
re++;
}
}
r=min(r, re);
}
return r;
}
int main(void) {
cin>>n;
cin.ignore();
while (n--) {
getline(cin, t);
b=0;
for (int j=0; j<12; j++) {
int m=11-j;
b|=t[j]=='o'?1<<m:0<<m;
}
memset(d, -1, sizeof(d));
cout<<dfs(b)<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 10364
again, didn't work it out until I saw other's solution, yes
this is a memorized search plus using bitmask representing states problem
why memorized search but not bottom-up?
because it's again a tree-structure DAG, I think...
whenever it's a tree-structure DAG, use top-down and it's much easier
also bitwise operations are included to transit state or calculate
state:
dp[i][j] - if can reach state i while have formed j sticks
transition:
when calc(i, j)==l, means state i can form j sticks
we only advance j by 1
else
dp[i][j]|=dp[k][j], for all k are pre states of i, means if i is 1111, then k could be
0111, 1011, 1101, 1110
this is a memorized search plus using bitmask representing states problem
why memorized search but not bottom-up?
because it's again a tree-structure DAG, I think...
whenever it's a tree-structure DAG, use top-down and it's much easier
also bitwise operations are included to transit state or calculate
state:
dp[i][j] - if can reach state i while have formed j sticks
transition:
when calc(i, j)==l, means state i can form j sticks
we only advance j by 1
else
dp[i][j]|=dp[k][j], for all k are pre states of i, means if i is 1111, then k could be
0111, 1011, 1101, 1110
/* UVas */
/*****************************************************************************/
int n, m, a, l;
int s[21];
int d[1<<20][4];
int calc(int state, int c) {
int r=0;
for (int i=0; i<m; i++) {
r+=(((1<<i)&state)>>i)*s[i];
}
return r-c*l;
}
int dfs(int state, int c) {
int &r=d[state][c];
int length=calc(state, c);
if (length==l) {
return dfs(state, c+1);
} else if (c==4) {
return 1;
} else if (r!=-1) {
return r;
} else {
r=0;
for (int i=0; i<m&&!r; i++) {
if (!(state&(1<<i))&&(length+s[i]<=l)) {
r|=dfs(state|(1<<i), c);
}
}
return r;
}
}
int main(void) {
cin>>n;
while (n--) {
cin>>m;
a=0;
for (int i=0; i<m; i++) {
cin>>s[i];
a+=s[i];
}
if (a%4) {
cout<<"no"<<endl;
} else {
l=a/4;
memset(d, -1, sizeof(d));
dfs(0, 0)?cout<<"yes":cout<<"no";
cout<<endl;
}
}
return 0;
}
/*****************************************************************************/
Google New York
unfortunately it's closed on weekends, plus anyone want to get in needs an appointment
anyway...google is at the 4th floor
anyway...google is at the 4th floor
UVa 11307
another tree dp problem, solved it until I see other's solution
state:
dp[i][j] - minimum color sum at node i colored color j
transition:
dp[i][j]+=min(dp[k][l]), for all k is i's child and for all l of 15 colors
so the dfs method would be like
don't know why it's 15 colors, maybe it's tried out?
state:
dp[i][j] - minimum color sum at node i colored color j
transition:
dp[i][j]+=min(dp[k][l]), for all k is i's child and for all l of 15 colors
so the dfs method would be like
void dfs(int current, int parent) {
if (sizeof(adj[current])) { /* internal node */
for (int i=1; i<=15; i++) {
dp[current][i]=i;
}
for (int i=0; i<sizeof(adj[current]); i++) {
int child=adj[current][i];
if (child==parent) continue; /* avoid cycle */
dfs(child, current);
for (int j=1; j<=15; j++) {
int tmp=INF;
for (int k=1; k<=15; k++) {
tmp=min(tmp, dp[child][k]);
}
dp[current][j]+=tmp;
}
}
} else { /* leaf node */
for (int i=1; i<=15; i++) {
dp[current][i]=i;
}
}
}
and the target state is min(dp[k][i]), for any arbitrary node k as root, and for all i of 15 colorsdon't know why it's 15 colors, maybe it's tried out?
UVa 10243
a tree dp problem, it's hard if you've never touched tree dp problem, but the idea blow the surface is the same with normal dp problem
state:
dp[i][0], dp[i][1] - 0 means minimum exits without choosing node i, while 1 means minimum exits with choosing node i
transition:
dp[i][0]+=dp[k][1]
dp[i][1]+=min(dp[k][0], dp[k][1]), for all k is i's children
there are 2 tricky things here if you wanna do it bottom-up
1 need to initialize all leaf nodes to d[leaf][0]=0, d[leaf][1]=1, judge on if sizeof(l[leaf])==1 to see whether a node is a leaf
2 however you still need to do a recursive traversal on all nodes, to get the DAG order
state:
dp[i][0], dp[i][1] - 0 means minimum exits without choosing node i, while 1 means minimum exits with choosing node i
transition:
dp[i][0]+=dp[k][1]
dp[i][1]+=min(dp[k][0], dp[k][1]), for all k is i's children
there are 2 tricky things here if you wanna do it bottom-up
1 need to initialize all leaf nodes to d[leaf][0]=0, d[leaf][1]=1, judge on if sizeof(l[leaf])==1 to see whether a node is a leaf
2 however you still need to do a recursive traversal on all nodes, to get the DAG order
/* UVas */
/*****************************************************************************/
int N, n, t;
int v[1001];
int d[1001][2];
vector<int> l[1001];
int dfs(int c, int p) {
int &r=d[c][p];
if (r!=-1) {
return r;
}
v[c]=1;
if (p) {
r=1;
for (int i=0; i<sz(l[c]); i++) {
if (v[l[c][i]]) {
continue;
}
r+=min(dfs(l[c][i], 0), dfs(l[c][i], 1));
}
} else {
r=0;
for (int i=0; i<sz(l[c]); i++) {
if (v[l[c][i]]) {
continue;
}
r+=dfs(l[c][i], 1);
}
}
v[c]=0;
return r;
}
int main(void) {
while (cin>>N&&N) {
for (int i=1; i<=N; i++) {
cin>>n;
l[i].clear();
for (int j=0; j<n; j++) {
cin>>t;
l[i].pb(t);
}
}
memset(d, -1, sizeof(d));
cout<<max(1, min(dfs(1, 0), dfs(1, 1)))<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 10702
again and again a simple and easy dp
state:
dp[i][j] - max profit when in city j at day i
transition:
dp[i][j]=max(dp[i][j], dp[i-1][k]+l[k][j]), 1<=k<=C
for all city k, if he was at city k yesterday, then we must have got the max profit of
dp[i-1][k], and then we add l[k][j] to the sum
state:
dp[i][j] - max profit when in city j at day i
transition:
dp[i][j]=max(dp[i][j], dp[i-1][k]+l[k][j]), 1<=k<=C
for all city k, if he was at city k yesterday, then we must have got the max profit of
dp[i-1][k], and then we add l[k][j] to the sum
/* UVas */
/*****************************************************************************/
int C, S, E, T;
int e[101];
int l[101][101];
int d[1001][101];
int main(void) {
while (cin>>C>>S>>E>>T&&C&&S&&E&&T) {
for (int i=1; i<=C; i++) {
for (int j=1; j<=C; j++) {
cin>>l[i][j];
}
}
for (int i=1; i<=E; i++) {
cin>>e[i];
}
memset(d, -1, sizeof(d));
d[0][S]=0;
for (int i=1; i<=T; i++) {
for (int j=1; j<=C; j++) {
for (int k=1; k<=C; k++) {
if (d[i-1][k]!=-1) {
d[i][j]=max(d[i][j], d[i-1][k]+l[k][j]);
}
}
}
}
int r=0;
for (int i=1; i<=E; i++) {
r=max(r, d[T][e[i]]);
}
cout<<r<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 10681
another simple and easy dp
state:
dp[i][j] - can be 0 or 1, whether can reach city j at day i
transition:
dp[i][j]=1 if l[k][j]&&d[i-1][k], 1<=k<=n
for all city k, if there is a link between k and j, and he was there yesterday
then of course he can reach city j today
state:
dp[i][j] - can be 0 or 1, whether can reach city j at day i
transition:
dp[i][j]=1 if l[k][j]&&d[i-1][k], 1<=k<=n
for all city k, if there is a link between k and j, and he was there yesterday
then of course he can reach city j today
/* UVas */
/*****************************************************************************/
int C, L, S, E, D, t1, t2;
int l[101][101];
int d[201][101];
int main(void) {
while (cin>>C>>L&&C>0&&L>=0) {
memset(l, 0, sizeof(l));
for (int i=0; i<L; i++) {
cin>>t1>>t2;
l[t1][t2]=1;
l[t2][t1]=1;
}
cin>>S>>E>>D;
memset(d, 0, sizeof(d));
d[0][S]=1;
for (int i=1; i<=D; i++) {
for (int j=1; j<=C; j++) {
for (int k=1; k<=C; k++) {
if (l[k][j]&&d[i-1][k]) {
d[i][j]=1;
}
}
}
}
d[D][E]?cout<<"Yes, Teobaldo can travel.":cout<<"No, Teobaldo can not travel.";
cout<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 910
simple dp problem again
state:
dp[i][j] - how many ways to reach point j with i steps
transition:
dp[i][j]+=dp[i-1][k], 1<=k<=26
do this on both when p[k][0]==j and when p[k][1]==j
state:
dp[i][j] - how many ways to reach point j with i steps
transition:
dp[i][j]+=dp[i-1][k], 1<=k<=26
do this on both when p[k][0]==j and when p[k][1]==j
/* UVas */
/*****************************************************************************/
char t0, t1, tx;
int n, m;
int p[27][3];
int d[31][27];
int main(void) {
while (cin>>n) {
for (int i=1; i<=n; i++) {
cin>>t0>>t0>>t1>>tx;
p[i][0]=t0-'@';
p[i][1]=t1-'@';
p[i][2]=tx=='x'?1:0;
}
cin>>m;
memset(d, 0, sizeof(d));
d[0][1]=1;
for (int i=1; i<=m; i++) {
for (int j=1; j<=n; j++) {
for (int k=1; k<=n; k++) {
if (p[k][0]==j) {
d[i][j]+=d[i-1][k];
}
if (p[k][1]==j) {
d[i][j]+=d[i-1][k];
}
}
}
}
int r=0;
for (int i=1; i<=n; i++) {
r+=d[m][i]*p[i][2];
}
cout<<r<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 590
being similar to TSP and shortest path problem
state:
dp[i][j] - minimum cost at city j on day i
transition:
dp[i][j]=min(dp[i-1][k]+f[k->j][i]), all k!=j and k->j refers to flight cost index
the first tricky thing is to set d[i][j]=-1 if it can't be reached
second one is how to calculate flight cost index
flight's index from k->j is (k-1)*(n-1)+j, then minus 1 if k<j
and flight cost's index on day i is i%d, or it's d if i%d==0
state:
dp[i][j] - minimum cost at city j on day i
transition:
dp[i][j]=min(dp[i-1][k]+f[k->j][i]), all k!=j and k->j refers to flight cost index
the first tricky thing is to set d[i][j]=-1 if it can't be reached
second one is how to calculate flight cost index
flight's index from k->j is (k-1)*(n-1)+j, then minus 1 if k<j
and flight cost's index on day i is i%d, or it's d if i%d==0
/* UVas */
/*****************************************************************************/
int n, k, c=1;
int f[91][31];
int d[1001][11];
int main(void) {
while (cin>>n>>k&&n&&k) {
for (int i=1; i<=n*(n-1); i++) {
cin>>f[i][0];
for (int j=1; j<=f[i][0]; j++) {
cin>>f[i][j];
}
}
memset(d, -1, sizeof(d));
for (int i=2; i<=n; i++) {
d[1][i]=f[i-1][1]==0?-1:f[i-1][1];
}
for (int i=2; i<=k; i++) {
for (int j=1; j<=n; j++) {
for (int l=1; l<=n; l++) {
if (l==j||d[i-1][l]==-1) {
continue;
}
int a=(l-1)*(n-1)+j;
a=l<j?a-1:a;
int b=i%f[a][0]==0?f[a][0]:i%f[a][0];
if (!f[a][b]) {
continue;
}
if (d[i-1][l]+f[a][b]<d[i][j]||d[i][j]==-1) {
d[i][j]=d[i-1][l]+f[a][b];
}
}
}
}
cout<<"Scenario #"<<c<<endl;
d[k][n]==-1?cout<<"No flight possible.":cout<<"The best flight costs "<<d[k][n]<<".";
cout<<endl<<endl;
c++;
}
return 0;
}
/*****************************************************************************/
UVa 11450
this is an easy problem can be solved by dp...
state:
dp[i][j] - whether can bought i garments with j units money
transition:
dp[i][j]=dp[i-1][j+g[i][k]], for 0<=k<t[i] if dp[i-1][j]
which means if we can buy i-1 garments with j units money then we can test all possibilities of garment i
state:
dp[i][j] - whether can bought i garments with j units money
transition:
dp[i][j]=dp[i-1][j+g[i][k]], for 0<=k<t[i] if dp[i-1][j]
which means if we can buy i-1 garments with j units money then we can test all possibilities of garment i
/* UVas */
/*****************************************************************************/
int c, m, C, K;
int g[20][20];
int t[20];
int d[20][201];
int main(void) {
cin>>c;
while (c--) {
cin>>m>>C;
for (int i=0; i<C; i++) {
cin>>t[i];
for (int j=0; j<t[i]; j++) {
cin>>g[i][j];
}
}
memset(d, 0, sizeof(d));
for (int i=0; i<t[0]; i++) {
if (m-g[0][i]>=0) {
d[0][g[0][i]]=1;
}
}
for (int i=1; i<C; i++) {
for (int j=0; j<=m; j++) {
if (d[i-1][j]) {
for (int k=0; k<t[i]; k++) {
d[i][j+g[i][k]]=1;
}
}
}
}
int f=0;
for (int i=m; i>=0; i--) {
if (d[C-1][i]) {
f=1;
cout<<i<<endl;
break;
}
}
if (!f) {
cout<<"no solution"<<endl;
}
}
return 0;
}
/*****************************************************************************/
UVa 10891
this is an extention of a classic dp game problem sum of a subsequnce can be represented by 1-d or 2-d array
state:
dp[i][j] - max difference of subsequnce i to j
the DAG here is (i+1, j), (i, j-1) -> (i, j)
this tells us the iteration order of states for j=1 to n-1, for i=0 to i+j
transtion:
dp[i][j]=max(dp[i][j], s[i][j]-dp[p][q]), i+1<=p<=j, i<=q<j
state:
dp[i][j] - max difference of subsequnce i to j
the DAG here is (i+1, j), (i, j-1) -> (i, j)
this tells us the iteration order of states for j=1 to n-1, for i=0 to i+j
transtion:
dp[i][j]=max(dp[i][j], s[i][j]-dp[p][q]), i+1<=p<=j, i<=q<j
/* UVas */
/*****************************************************************************/
int n;
int a[100];
int s[101];
int d[100][100];
int main(void) {
while (cin>>n&&n) {
for (int i=0; i<n; i++) {
cin>>a[i];
s[i+1]=s[i]+a[i];
}
memset(d, 0, sizeof(d));
for (int i=0; i<n; i++) {
d[i][i]=a[i];
}
for(int j=1; j<n; j++){
for(int i=0; i+j<n; i++){
int m=0;
for(int k=i+1; k<=i+j; k++) {
m=min(m, d[k][i+j]);
}
for(int k=i; k<i+j; k++) {
m=min(m, d[i][k]);
}
d[i][i+j]=s[i+j+1]-s[i]-m;
}
}
cout<<2*d[0][n-1]-s[n]<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 10337
the same with UVa 116 with more restrictions, and target state is dp[9][X/100] but not dp[9][X/100-1], so...
state:
dp[i][j] - minimum fuel used at altitude i and distance j
transition:
dp[i][j]=min(dp[i][j], dp[p[k]][j-1]+cost) for all 0<k<3
the restriction is resolved with setting cost of them equal to HOLD altitude's cost
state:
dp[i][j] - minimum fuel used at altitude i and distance j
transition:
dp[i][j]=min(dp[i][j], dp[p[k]][j-1]+cost) for all 0<k<3
the restriction is resolved with setting cost of them equal to HOLD altitude's cost
/* UVas */
/*****************************************************************************/
int c, x;
int main(void) {
cin>>c;
while (c--) {
cin>>x;
int w[10][x/100];
int d[10][x/100+1];
for (int i=0; i<10; i++) {
for (int j=0; j<x/100; j++) {
cin>>w[i][j];
}
}
for (int i=0; i<10; i++) {
for (int j=0; j<=x/100; j++) {
d[i][j]=INT_MAX;
}
}
d[9][0]=0;
for (int j=1; j<=x/100; j++) {
for (int i=0; i<10; i++) {
int p[3]={i==0?i:i-1, i, i==9?i:i+1};
int c[3]={i==0?-w[i][j-1]:-w[i-1][j-1], -w[i][j-1], i==9?-w[i][j-1]:-w[i+1][j-1]};
int C[3]={20, 30, 60};
for (int k=0; k<3; k++) {
if (d[p[k]][j-1]==INT_MAX) {
continue;
}
int cost=C[k]+c[k];
d[i][j]=min(d[i][j], d[p[k]][j-1]+cost);
}
}
}
cout<<d[9][x/100]<<endl<<endl;
}
return 0;
}
/*****************************************************************************/
UVa 607
focus on minimum lectures first, i must come before i+1, so we have
state:
dp[i] - minimum lectures overlaps i topics
transition:
dp[i]=min(dp[j]+1), for all 0<j<i and L-(t[i]-t[j])>0
L-(t[i]-t[j])>0 means time left is enough to overlap t[j] till t[i] only when minimum lectures of two equals shall we consider about minimum DI
state:
dp[i] - minimum DI overlaps i topics
transition:
dp[i]=min(dp[j]+DI(L-(t[i]-t[j])), for all 0<j<i and L-(t[i]-t[j])>0
state:
dp[i] - minimum lectures overlaps i topics
transition:
dp[i]=min(dp[j]+1), for all 0<j<i and L-(t[i]-t[j])>0
L-(t[i]-t[j])>0 means time left is enough to overlap t[j] till t[i] only when minimum lectures of two equals shall we consider about minimum DI
state:
dp[i] - minimum DI overlaps i topics
transition:
dp[i]=min(dp[j]+DI(L-(t[i]-t[j])), for all 0<j<i and L-(t[i]-t[j])>0
/* UVas */
/*****************************************************************************/
int n, L, C, c=1;
int t[1001];
int d1[1001];
int d2[1001];
int di(int time) {
return time==0?0:time<=10?-C:(time-10)*(time-10);
}
int main(void) {
while (cin>>n&&n) {
cin>>L>>C;
if (c>1) {
cout<<endl;
}
for (int i=1; i<=n; i++) {
cin>>t[i];
t[i]+=t[i-1];
}
memset(d1, -1, sizeof(d1));
memset(d2, -1, sizeof(d2));
d1[0]=0;
d2[0]=0;
for (int i=1; i<=n; i++) {
for (int j=i-1; j>=0&&t[i]-t[j]<=L; j--) {
int d=di(L-(t[i]-t[j]));
if (d1[i]<0||d1[i]>d1[j]+1) {
d1[i]=d1[j]+1;
d2[i]=d2[j]+d;
}
if (d1[i]==d1[j]+1&&(d2[i]>d2[j]+d||d2[i]==-1)) {
d2[i]=d2[j]+d;
}
}
}
cout<<"Case "<<c<<":"<<endl;
cout<<"Minimum number of lectures: "<<d1[n]<<endl;
cout<<"Total dissatisfaction index: "<<d2[n]<<endl;
c++;
}
return 0;
}
/*****************************************************************************/
UVa 473
base on traditional 0/1 knapsack dp, here we have multiple knapsacks
therefore DP matrix turns to 3 dimensions
the 3rd transformation is what makes this different from traditional 0/1 knapsack dp
state:
dp[i][j][k] - iterates songs with i while k minutes left in disk j
transformation:
if k>=s[i], means can add song i
dp[i+1][j][k]=max(dp[i][j][k], dp[i][j][k-s[i]]+1)
or k<s[i], means no more song can be added to disk j
dp[i+1][j][k]=dp[i][j][k]
fall through, we check if more songs can be added to a new disk if j>0, means there are still other disks to use
dp[i+1][j][k]=max(dp[i+1][j][k], dp[i][j-1][t-s[i]]+1)
the 3rd transformation is what makes this different from traditional 0/1 knapsack dp
state:
dp[i][j][k] - iterates songs with i while k minutes left in disk j
transformation:
if k>=s[i], means can add song i
dp[i+1][j][k]=max(dp[i][j][k], dp[i][j][k-s[i]]+1)
or k<s[i], means no more song can be added to disk j
dp[i+1][j][k]=dp[i][j][k]
fall through, we check if more songs can be added to a new disk if j>0, means there are still other disks to use
dp[i+1][j][k]=max(dp[i+1][j][k], dp[i][j-1][t-s[i]]+1)
/* UVas */
/*****************************************************************************/
int c, n, t, m, tmp;
int d[800][100][100];
int s[800];
int main(void) {
cin>>c;
while (c--) {
cin>>n>>t>>m;
int p=0;
scanf("%d", s+p++);
for (int i=1; i<n; i++) {
scanf(", %d", s+p++);
}
memset(d, 0, sizeof(d));
for (int i=0; i<n; i++) {
for (int j=0; j<=m; j++) {
for (int k=0; k<=t; k++) {
if (k<s[i]) {
d[i+1][j][k]=d[i][j][k];
} else {
d[i+1][j][k]=max(d[i][j][k], d[i][j][k-s[i]]+1);
}
if (j>0) {
d[i+1][j][k]=max(d[i+1][j][k], d[i][j-1][t-s[i]]+1);
}
}
}
}
int r=0;
for (int i=0; i<=n; i++) {
r=max(r, d[i][m][0]);
}
cout<<r<<endl;
if (c) {
cout<<endl;
}
}
return 0;
}
/*****************************************************************************/
Subscribe to:
Posts
(
Atom
)