DARK SOULS: 永久保持人性(仅外表)

活尸状态简直丑到爆:..

char jmp=0xeb;
DWORD off=0x98610b;
DWORD old;
DWORD awe=addr+off;

VirtualProtect((void*)(awe+1), 1, PAGE_EXECUTE_READWRITE, &old);
WriteProcessMemory(pro, (void*)(awe), &jmp, 1, NULL);
VirtualProtect((void*)(awe+1), 1, old, &old);

1个字节的事情..指令地址就是DATA.exe+0x0098610b喽

内存管理: Buddy system

/* Buddy system algorithm */

/* Written by Kai Wang */
using namespace std;

#include <cstring>
#include <cmath>
#include <sstream>
#include <iostream>
#include <vector>
#include <utility>

#define FOR(i, a, b) for (int i=(a); i<=(b); i++)
#define REP(i, a)       for (int i=0; i<(a); i++)
#define all(a)             (a).begin(), (a).end()
#define sz(a)                   (int)((a).size())
#define mp                              make_pair
#define y                                  second
#define x                                   first

#define MEMO_SIZE                              21

int main() {

    /* first of pair is rank of block size, 
       second is it's process */
    vector<pair<int, char> > memo;

    /* 2 MB, '*' indicates empty block  */
    memo.insert(memo.begin(), mp(MEMO_SIZE, '*'));

    string cmd;
    while (cin>>cmd) {
        cout<<cmd<<" ";
        char wh=cmd[0]; cin>>cmd;
        cout<<cmd<<endl;
        char op=cmd[0];
        stringstream ss(cmd.substr(1));
        int size; ss>>size;
        int r=floor(log2(size*1024))+1;
        typeof(memo.begin()) it;
        if (op=='+') {
            it=find(all(memo), mp(r, '*'));
            /* found an empty block of rank r */
            if (it!=memo.end()) {
                it->y=wh;
                goto next;
            }
            /* divide the first available larger block */
            FOR(i, r+1, MEMO_SIZE) {
                it=find(all(memo), mp(i, '*'));
                if (it==memo.end())
                    continue;
                int time=i-r;
                while (time--) {
                    it=memo.erase(it);
                    it=memo.insert(it, mp(i-1, '*'));
                    it=memo.insert(it, mp(i-1, '*'));
                    i--;
                }
                it->y=wh;
                break;
            }
        } else {
            it=find(all(memo), mp(r, wh));
            it->y='*';
            /* try merge neighbour block, left first, than right */
            while (it->y=='*') {
                int id=it-memo.begin();
                if (id>=1 && memo[id-1].x==r && memo[id-1].y=='*') {
                    it--;
                    it=memo.erase(it);
                    it=memo.erase(it);
                    it=memo.insert(it, mp(r+1, '*'));
                    r++;
                    goto next_try;
                } else if (id<MEMO_SIZE && memo[id+1].x==r &&
                           memo[id+1].y=='*') {
                    it=memo.erase(it);
                    it=memo.erase(it);
                    it=memo.insert(it, mp(r+1, '*'));
                    r++;
                    goto next_try;
                }
                break;
next_try:;
            }
        }
next:
        REP(i, sz(memo)) {
            cout<<(int)pow(2, memo[i].x)/1024<<memo[i].y;
            if (i==sz(memo)-1)
                cout<<endl;
            else
                cout<<"  ";
        }
        cout<<endl;
    }
    return 0;
}

Codeforces 202 DIV2 C

简单的二分查找:..

#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 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

/* 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

/* 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.

/* 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...

/* 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...

/* 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

/* 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

/* 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...

/* 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...

/* 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

/* 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

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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

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

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 colors
don'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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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

/* 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)

/* 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;
}
/*****************************************************************************/