uva--10602+貪心

uva--10602+貪心

題意：

某公司開發了一個編輯器，支持兩條語音命令：1.重復最後一個單詞，2.刪除最後一個單詞的最後一個字母。給你一系列的單詞，問利用編輯器的功能最少需要輸入多少個字母就可以將所有單詞輸入；要求第一個單詞一定要第一個輸入，其余單詞不限順序。

思路：

輸入第一個單詞後，我們可以怎麼樣選擇能使得輸入的字母數最少？當然我們需要選擇和第一個單詞有最長公共前綴的單詞；這就是貪心的策略：每次都選擇和上一次輸入單詞有最長公共前綴的單詞輸入。

代碼如下：

#include
#include
#include
using namespace std;

int cnt(char *str1,char *str2)
{
     int len1=strlen(str1),i;
     for(i=0;i=max1)
                {
                    max1=num;
                    temp=j;
                }
            }
            cnt1++;
            sum+=(strlen(str[temp])-max1);
            vis[temp]=1;
            ans[k++]=temp;
            i=temp;
        }
        printf("%d\n",sum);
        for(i=0;i