递推DP UVA 1424 Salesmen

题目传送门

 /*

    题意：给定包含n个点的无向图和一个长度为L的序列，修改尽量少的点使得相邻的数字相同或连通

    DP：状态转移方程：dp[i][j] = min (dp[i][j], dp[i-1][k] + (j != a[i]));

         dp[i][j]表示前i个数字以j结尾的最小花费。我自己写了很长时间，很复杂，状态转移的不好。

         应该能知道前一个状态的所有情况，每一维数组记录的就是一个状态

 */

 /************************************************

 Author        :Running_Time

 Created Time  :2015-8-5 9:03:34

 File Name     :UVA_1424.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 1e2 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 bool con[MAXN][MAXN];

 int a[MAXN*];

 int dp[MAXN*][MAXN];

 int n1, m, n;

 int work(void)  {

     memset (dp, INF, sizeof (dp));

     for (int i=; i<=n1; ++i)   {

         dp[][i] = (i != a[]);

     }

     for (int i=; i<=n; ++i)    {

         for (int j=; j<=n1; ++j)   {

             for (int k=; k<=n1; ++k)   {

                 if (con[j][k])  {

                     dp[i][j] = min (dp[i][j], dp[i-][k] + (j != a[i]));

                 }

             }

         }

     }

     int res = INF;

     for (int i=; i<=n1; ++i)    {

         res = min (res, dp[n][i]);

     }

     return res;

 }

 int main(void)    {     //UVA 1424 Salesmen

     int T;  scanf ("%d", &T);

     while (T--) {

         scanf ("%d%d", &n1, &m);

         memset (con, false, sizeof (con));

         for (int i=; i<=n1; ++i)   con[i][i] = true;

         for (int i=; i<=m; ++i)    {

             int u, v;   scanf ("%d%d", &u, &v);

             con[u][v] = con[v][u] = true;

         }

         scanf ("%d", &n);

         for (int i=; i<=n; ++i)    {

             scanf ("%d", &a[i]);

         }

         printf ("%d\n", work ());

     }

     return ;

 }

 /************************************************

 Author        :Running_Time

 Created Time  :2015-8-5 9:03:34

 File Name     :UVA_1424.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 1e2 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 bool con[MAXN][MAXN];

 vector<int> G[MAXN];

 vector<int> pre;

 int a[MAXN*];

 int dp[MAXN][][MAXN];

 int n1, m, n;

 int work(void)  {

     memset (dp, INF, sizeof (dp));    pre.clear ();

     dp[][][a[]] = ;

     for (int i=; i<=n1; ++i)   {

         if (i == a[])  continue;

         pre.push_back (i);

         dp[][][i] = ;

     }

     for (int i=; i<=n; ++i)    {

         if (con[a[i-]][a[i]])  {

             dp[i][][a[i]] = dp[i-][][a[i-]];

             pre.clear ();   continue;

         }

         vector<int> tmp;

         for (int j=; j<pre.size (); ++j)   {

             int u = pre[j];

             for (int k=; k<G[u].size (); ++k) {

                 int v = G[u][k];

                 if (con[u][v])  {

                     if (v == a[i])  dp[i][][v] = min (dp[i][][v], dp[i-][][u]);

                     else    dp[i][][v] = min (dp[i][][v], dp[i-][][u] + );

                     tmp.push_back (v);

                 }

             }

         }

         pre.clear ();

         for (int j=; j<tmp.size (); ++j)   pre.push_back (tmp[j]);

     }

     int res = INF;

     res = min (res, dp[n][][a[n]]);

     for (int i=; i<pre.size (); ++i)   {

         int v = pre[i];

         res = min (res, dp[n][][v]);

     }

     //debug

     for (int i=; i<=n; ++i)    {

         printf ("%d ", dp[i][][a[i]]);

     }

     puts ("");

     return res;

 }

 int main(void)    {

     int T;  scanf ("%d", &T);

     while (T--) {

         scanf ("%d%d", &n1, &m);

         memset (con, false, sizeof (con));

         for (int i=; i<=n1; ++i)   G[i].clear ();

         for (int i=; i<=n1; ++i)   con[i][i] = true;

         for (int i=; i<=m; ++i)    {

             int u, v;   scanf ("%d%d", &u, &v);

             con[u][v] = con[v][u] = true;   G[u].push_back (v); G[v].push_back (u);

         }

         scanf ("%d", &n);

         for (int i=; i<=n; ++i)    {

             scanf ("%d", &a[i]);

         }

         printf ("%d\n", work ());

     }

     return ;

 }

undone(感受一下就行了)

巴特西

递推DP UVA 1424 Salesmen

最新文章

热门文章